perm filename V2Q.IN[TEX,DEK] blob
sn#285506 filedate 1977-05-28 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 725 galley 1
C00026 00003 folio 731 galley 2
C00046 00004 folio 735 galley 3
C00070 00005 folio 742 galley 4
C00096 00006 folio 748 galley 5
C00117 00007 folio 754 galley 6
C00139 00008 folio 758 galley 7
C00160 00009 folio 761 galley 8
C00174 00010
C00175 00011
C00176 ENDMK
C⊗;
folio 725 galley 1
0 {U0}{H9L11M29}|π58320#Computer Programming!(Knuth/Addison-We
1 sley)!f. 725!Ans!g. 1c|'{A6}|9|1|9|1|4|1|9|4|↔d|(.|4.|4.|4,|
4 4|εa|β3,|5a|β2,|5a|β1,|5a|β0;|5a|βα_↓|β1,|5a|βα_↓|β2,|5.|4.|
4 4.|'5.|4.|4.|4,|4b|β3,|4b|β2,|4b|β1,|4b|β0;|4b|βα_↓|β1,|4b|β
5 α_↓|β2,|4.|4.|4.|)|↔f|4α=↓|4|↔d|(.|4.|4.|4,|4A|β3,|4A|β2,|4A
5 |β1,|4A|β0:|4A|βα_↓|β1,|4A|βα_↓|β2,|4.|4.|4.|d5.|4.|4.|4,|4B
5 |β3,|4B|β2,|4B|β1,|4B|β0:|4B|βα_↓|β1,|4B|βα_↓|β2,|4.|4.|4.|)
5 |↔F|'{A4}|πif!!|εA|βj|4α=↓|4|↔d|(a|βk|mj|mα+↓|m1|βα_↓|β1,|4|
6 1a|βk|mj|mα+↓|m1|βα_↓|β2,|4.|4.|4.|4,|5a|βk|mj|d5|ha|βk|mj|m
6 α+↓|m1|βα_↓|β1,|5|nb|βk|mj|mα+↓|m1|βα_↓|β2,|4.|4.|4.|4,|4b|β
6 k|mj|)|↔f,|4B|βj|4α=↓|4b|βk|mj|mα+↓|m1|βα_↓|β1|4.|4.|4.|4b|β
6 k|mj,|;{A9}|πwhere |↔b|εk|βn|↔v |πis any in_nite
12 sequence of integers with |εk|βj|βα+↓|β1|4|¬Q|4k|βj.|'
17 {A3}|π|≡1|≡1|≡.|9|4(The following algorithm works
21 both for addition or subtraction, depending on
28 whether the plus or minus sign is chosen.)|'!!|2Start
37 by setting |εk|4|¬L|4a|βn|βα+↓|β1|4|¬L|4a|βn|βα+↓|β2|4|¬L|4b
39 |βn|βα+↓|β1|4|¬L|4b|βn|βα+↓|β2|4|¬L|40; |πthen
41 for |εm|4α=↓|40, 1, . . . , n|4α+↓|42 |πdo the
51 following : Set |εc|βm|4|¬L|4a|βm|4|¬N|4b|βm|4α+↓|4k;
55 |πthen if |εc|βm|4|¬R|42, |πset |εk|4|¬L|4|→α_↓1
60 |πand |εc|βm|4|¬L|4c|βm|4α_↓|42; |πif |εc|βm|4|¬W|40,
64 |πset |εk|4|¬L|41 |πand |εc|βm|4|¬L|4c|βm|4α+↓|42;
68 |πand if 0|4|¬E|4|εc|βm|4|¬E|41, |πset |εk|4|¬L|40.|'
73 {A3}|π|≡1|≡2|≡.|9|4(a) Subtract (.|4.|4.|4|εa|β30a|β10)
76 |πfrom (.|4.|4.|4a|β40a|β20a|β0) |πin the negative
81 binary system. (b) Subtract (.|4.|4.|4|εb|β30b|β10)
86 |πfrom (.|4.|4.|4|εb|β40b|β20b|β0) |πin the binary
91 system.|'{A3}|≡1|≡3|≡.|9|4(1.90909090|4.|4.)|4α=↓|4(0.090909
92 |4.|4.)|4α=↓|4|f1|d311|).|'{A3}|≡1|≡4|≡.|9|4!!!!|4|∂1|91|93|
93 92|91!!|∂[5|4α_↓|44|εi]|'|L1|91|93|92|91|L[5|4α_↓|44i]>
95 {B2}|L#####>|L1|91|93|92|91>| 1|9|L1|92|90|92>
98 | 1|92|9|L1|92|93>| 1|91|93|9|L2|91>| 1|91|93|92|9|L1>
101 {B2}|9|1|9|1|4|1|9|4###########|'| 0|91|90|93|9|L1|91|92|90|
102 91|L[9|4α_↓|440i]>{A3}|π|≡1|≡5|≡.|9|4[|→α_↓|f10|d311|),|4|f1
103 |d311|)], and the rectangle shown in Fig. A<6.|'
111 {A4}|≡F|≡i|≡g|≡. |≡A|≡<|≡6|≡.|9|4Fundamental
113 region for quater-imaginary numbers.|'{A3}|≡1|≡6|≡.|9|4It
118 is tempting to try to do this in a very simple
129 way, by using the rule 2|4α=↓|4(1100)|ε|βi|βα_↓|β1
135 |πto take care of carries; but that leads to
144 a nonterminating method if we try to add one
153 to (11101)|ε|βi|βα_↓|β1|4α=↓|4|→α_↓1.|'!!|2|πThe
156 following solution does this by providing four
163 related algorithms (namely for adding or subtracting
170 1 or |εi). |πIf |ε|≤a |πis a string of zeros
180 and ones, let |ε|≤a|gP |πbe a string of zeros
189 and ones such that |ε(|≤a|gP)|βi|βα_↓|β1|4α=↓|4(|≤a|gP)|βi|β
193 α_↓|β1|4α+↓|41; |πand let |ε|≤a|gα_↓|gP, |≤a|gQ,
198 |≤a|gα_↓|gQ |πbe de_ned similarly, with |→α_↓1,
204 |→α+↓|εi, |πand |ε|→α_↓i |πrespectively in place
210 of |→α+↓1. Then|'{A9}|ε|h(|≤ax0)|gα_↓|gP|4|∂α=↓|4|≤a|gα_↓|gQ
213 x1; (|≤a1)|gα_↓|gP|4α=↓|4|≤a0.!!(|≤a0)|gα_↓|gQ|4|∂α=↓|4|≤a|g
214 Q1; (|≤a1)|gα_↓|gQ|4α=↓|4|≤a|gα_↓|gP0.|E|n|;| (|≤a0)|gP|4|Lα
216 =↓|4|≤a1; (|≤ax1)|gP|4α=↓|4|≤a|gQx0.| (|≤a0)|gQ|4|Lα=↓|4|≤a|
217 gP1; (|≤a1)|gQ|4α=↓|4|≤a|gα_↓|gQ0.>| (|≤ax0)|gα_↓|gP|4|Lα=↓|
219 4|≤a|gα_↓|gQx1; (|≤a1)|gα_↓|gP|4α=↓|4|≤a0.| (|≤a0)|gα_↓|gQ|4
220 |Lα=↓|4|≤a|gQ1; (|≤a1)|gα_↓|gQ|4α=↓|4|≤a|gα_↓|gP0.>
222 {A9}|πHere |εx |πstands for either 0 or 1, and
231 the strings are extended on the left with zeros
240 if necessary. The processes will clearly always
247 terminate. Hence every number of the form |εa|4α+↓|4bi
255 |πwith |εa, b |πintegers is representable in
262 the |εi|4α_↓|41 |πsystem.|'{A3}|≡1|≡7|≡.|9|4No;
266 the number |→α_↓1 cannot be so represented. (This
274 can be proved by constructing a set |εS |πas
283 in Fig. 1. We have the representations |ε|→α_↓i|4α=↓|4(0.111
290 1111|4.|4.|4.)|β1|βα+↓|βi, i|4α=↓|4(100.1111111|4.|4.|4.)|g1
291 |gα+↓|gi, |πbut |εS |πcontains no integer points
298 besides 0 and |ε|βα_↓i.) |πSee exercise 28, however.|'
306 {A3}|≡1|≡8|≡.|9|4Let |εS|β0 |πbe the set of points
313 (|εa|β7a|β6a|β5a|β4a|β3a|β2a|β1a|β0)|βi|βα_↓|β1,
314 |πwhere each |εa|βk |πis 0 or 1. |ε(S|β0 |πis
323 given by the 256 interior dots shown in Fig.
332 1, if that picture is multiplied by 16.) We _rst
342 show that |εS |πis closed: If |εy|β1, y|β2, .
351 . . |πis an in_nite subset of |εS, |πwe have
361 |εy|βn|4α=↓|4|¬K|βk|β|¬R|β1|4a|βn|βk16|gα_↓|gk,
362 |πwhere each |εa|βn|βk |πis in |εS|β0. |πConstruct
369 a tree whose nodes are |ε(a|βn|β1,|4.|4.|4.|4,|4a|βn|βr),
375 |πfor |ε1|4|¬E|4r|4|¬E|4n, |πand let a node of
382 this tree be an ancestor of another node if it
392 is an initial subsequence of that node. By the
401 in_nity lemma this tree has an in_nite path |ε(a|β1,
410 a|β2, a|β3, . . .), |πand so |ε|¬K|βk|β|¬R|β1|4a|βk16|gα_↓|g
417 k |πis a limit point of |ε|¬Ty|β1,|4y|β2,|4.|4.|4.|¬Y
424 |πin |εS.|'!!|2|πBy the answer to exercise 16,
432 all numbers of the form |ε(a|4α+↓|4bi)/16|gk
438 |πare representable, when |εa |πand |εb |πare
445 integers. Therefore if |εx |πand |εy |πare arbitrary
453 reals and |εk|4|¬R|41, |πthe number |εz|βk|4α=↓|4(|"l16|gkx|
458 "L|4α+↓|4|"l16|gky|"Li)/16|gk |πis in |εS|4α+↓|4m|4α+↓|4ni
462 |πfor some integers |εm |πand |εn. |πIt can be
471 shown that |εS|4α+↓|4m|4α+↓|4ni |πis bounded
476 away from the origin when |ε(m,|4n)|4|=|↔6α=↓|4(0,|40).
482 |πConsequently if |ε|¬Gx|¬G |πand |ε|¬Gy|¬G |πare
488 su∃ciently small and |εk |πis su∃ciently large,
495 we have |εz|βk|4|¬A|4S, |πand lim|ε|βk|β|¬M|β|¬X|4z|βk|4α=↓|
499 4x|4α+↓|4yi|4|¬A|4S.|'{A3}|π|≡1|≡9|≡.|9|4If |εm|4|¬Q|4u
502 |πor |εm|4|¬W|4l, |π_nd |εa|4|¬A|4D |πsuch that
508 |εm|4|"o|4a |π(modulo|4|εb); |πthe desired representation
513 will be a representation of |εm|¬S|4α=↓|4(m|4α_↓|4a)/b
519 |πfollowed by |εa. |πNote that |εm|4|¬Q|4u |πimplies
526 |εl|4|¬W|4m|¬S|4|¬W|4m; m|4|¬W|4l |πimplies |εm|4|¬W|4m|¬S|4
529 |¬W|4u; |πso the algorithm terminates.|'!!|2[There
535 are no solutions when |εb|4α=↓|42. |πThe representation
542 will be unique i= 0|4|¬A|4|εD; |πnonunique representation
549 occurs for example when |εD|4α=↓|4|¬T|→α_↓3,
554 |→α_↓1, 7|¬Y, b|4α=↓|43, |πsince |ε(|≤a)|β3|4α=↓|4(|=∩377|=∩
558 3|≤a)|β3. |πWhen |εb|4|¬E|43 |πit is not di∃cult
565 to show that there are exactly 2|ε|gb|gα_↓|g3
572 |πsolution sets |εD |πin which |¬G|εa|¬G|4|¬W|4b
578 |πfor all |εa|4|¬A|4D. |πFurthermore the set
584 |εD|4α=↓|4|¬T0, 1, 2|4α_↓|4|≤e|β2b|gn, 3|4α_↓|4|≤eb|gn,|4.|4
587 .|4.|4, b|4α_↓|42|4α_↓|4|≤e|βb|βα_↓|β2b|gn, b|4α_↓|41|4α_↓|4
589 b|gn|¬Y |πgives unique representations, for all
595 |εb|4|¬R|43 |πand |εn|4|¬R|41, |πwhen each |ε|≤e|βj
601 |πis 0 or 1.]|'{A3}|≡2|≡0|≡.|9|4(a) 0.|=∩1|=∩1|=∩1|4.|4.|4.|
606 4α=↓|4|=∩1.888|4.|4.|4.|4α=↓|4|=∩18.|f1|d57|)|f1|d57|)|f1|d5
606 7|)|4.|4.|4.|4α=↓|4|=∩18|f1|d57|).|f222|d5666|)|4|¬O|4|¬O|4|
606 ¬O|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4|=∩18|f123456|d5765432|).|f777|
606 d51111|))*?|≡2|≡0|≡.|9|4(a) 0.|=∩1|=∩1|=∩1|4.|4.|4.|4α=↓|4|=∩
607 1.888|4.|4.|4.|4α=↓|4|=∩18.|f1|d57|)|f1|d57|)|f1|d57|)|4.|4.
607 |4.|4α=↓|4|=∩18|f1|d57|).|f222|d5666|)|4|¬O|4|¬O|4|¬O|4α=↓|4
607 |¬O|4|¬O|4|¬O|4α=↓|4|=∩18|f123456|d5765432|).|f777|d5111|)|4
607 .|4.|4. has nine representations. (b) A |ε``D-|πfraction''
614 |ε.a|β1a|β2|4.|4.|4. |πalways lies between |→α_↓1/9
619 and |→α+↓71/9. Suppose |εx |πhas ten or more
627 |εD-|πdecimal representations. Then for su∃ciently
632 large |εk, 10|gkx |πhas ten representations which
639 di=er to the left of the decimal point: 10|ε|gkx|4α=↓|4n|β1|
647 4α+↓|4f|β1|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4n|β1|β0|4α+↓|4f|β1|β0
648 |πwhere |εf|βj |πis a |εD-|πfraction. By uniqueness
655 of integer representations, the |εn|βj |πare
661 distinct, say |εn|β1|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4n|β1|β0,
664 |πhence |εn|β1|β0|4α_↓|4n|β1|4|¬R|49; |πbut this
668 implies |εf|β1|4α_↓|4f|β1|β0|4|¬R|49|4|¬Q|471/9|4α_↓|4(|→α_↓
669 1/9), |πa contradiction. (c) Any number of the
677 form |ε0.a|β1a|β2|4.|4.|4.|4, |πwhere each |εa|βj
682 |πis |→α_↓1 or 8, equals |=∩1.|εa|ur|↔8|)1|)a|ur|↔8|)2|)|4.|
687 4.|4.|4|πwhere |εa|ur|↔0|)j|)|4α=↓|4a|βj|4α+↓|49
689 |π(and it even has six |εmore |πrepresentations
696 |=∩18.|εa|ur|¬C|)1|)a|ur|¬C|)2|)|4.|4.|4. |πetc.).|'
698 {A3}|≡2|≡1|≡.|9|4We can convert to such a representation
705 by using a method like that suggested in the
714 test for converting to balanced ternary.|'!!|2In
721 contrast to the systems of exercise 20, zero
729 can be represented in in_nitely many ways, all
737 obtained from |f1|d32|)|4α+↓|4|¬K|ε|βk|β|¬R|β1|4|→α_↓4|f1|d3
739 2|)|4|¬O|410|gα_↓|gk |πor from the negative of
745 this representation, by multiplying it by a power
753 of ten. The representations of unity are 1|f1|d32|)|4α_↓|4|f
760 1|d32|), |f1|d32|)|4α+↓|4|f1|d32|), 5|4α_↓|43|f1|d32|)|4α_↓|
762 4|f1|d32|), 5|4α_↓|44|f1|d32|)|4α+↓|4|f1|d32|),
764 50|4α_↓|445|4α_↓|43|f1|d32|)|4α_↓|4|f1|d32|),
765 50|4α_↓|445|4α_↓|44|f1|d32|)|4α+↓|4|f1|d32|),
766 etc., where |→|¬N|f1|d32|)|4α=↓|4(|→|¬N4|f1|d32|))(10|gα_↓|g
768 1|4α+↓|410|gα_↓|g2|4α+↓|4.|4.|4.). [|εAMM |≡5|≡7
771 (1950), 90<93.]|'{A3}|π|≡2|≡2|≡.|9|4Assuming
774 that we have some approximation |εb|βn|4.|4.|4.|4b|β1b|β0
780 |ππ*?|π|≡2|≡2|≡.|9|4Assuming that we have some
785 approximation |εb|βn|4.|4.|4.|4b|β1b|β0 |πwith
788 error |¬K|ε|β0|β|¬E|βk|β|¬E|βn|4b|βk10|gk|4α_↓|4x|4|¬Q|410|g
789 α_↓|gt |πfor |εt|4|¬Q|40, |πwe will show how
796 to reduce the error by approximately 10|ε|gα_↓|gt.
803 |π(The process can be started by _nding a suitable
812 |¬K|ε|β0|β|¬E|βk|β|¬E|βn|4b|βk10|gk|4|¬Q|4x;
813 |πthen a _nite number of reductions of this type
822 will make the error less than |ε|≤e.) |πSimply
830 choose |εm|4|¬Q|4n |πso large that the decimal
837 representation of |ε|→α_↓10|gm|≤a |πhas a one
843 in position |ε10|gα_↓|gt |πand no ones in positions
851 10|ε|gα_↓|gt|gα+↓|g1, 10|gα_↓|gt|gα+↓|g2,|4.|4.|4.|4,|410|gn
852 . |πThen |ε10|gm|≤a|4α+↓|4|π(a suitable sum of
858 powers of 10 between |ε10|gm |πand |ε10|gn)|4α+↓|4|¬K|β0|β|¬
864 E|βk|β|¬E|βn|4b|βk10|gk|4|¬V|4|¬K|β0|β|¬E|βk|β|¬E|βn|4b|βk10
864 |gk|4α_↓|410|gα_↓|gt.|'{A3}|π|≡2|≡3|≡.|9|4The
866 set |εS|4α=↓|4|¬T|¬K|βk|β|¬R|β1|4a|βkb|gα_↓|gk|4|¬G|4a|βk|4|
867 ¬A|4D|¬T |πis closed as in exercise 18, hence
875 measurable, and in fact it has positive measure.
883 Since |εbS|4α=↓|4|↔w|βa|β|¬A|βD|4(a|4α+↓|4S),
885 |πwe have |εb|≤m(S)|4α=↓|4|≤m(bS)|4|¬E|4|¬K|βa|β|¬A|βD|4|≤m(
887 a|4α+↓|4S)|4α=↓|4|¬K|βa|β|¬A|βd|4|≤m(S)|4α=↓|4b|≤m(S),
888 |πand we must have |ε|≤m{H11}({H9}(a|4α+↓|4S)|4|↔Q|4(a|¬S|4α
892 +↓|4S){H11}){H9}|4α=↓|40 |πwhen |εa|4|=|↔6α=↓|4a|¬S|4|¬A|4D.
894 |πNow |εT |πis a union of countably many sets
904 of the form |ε10|gk{H11}({H9}n|4α+↓|4((a|4α+↓|4S)|4|↔Q|4(a|¬
907 S|4α+↓|4S)){H11}){H9}, a|4|=|↔6α=↓|4a|¬S, |πeach
910 of measure zero.|'!!|2[The set |εT |πcannot be
918 empty, since the real numbers cannot be written
926 as a countable union of disjoint, closed, bounded
934 sets. If |εD |πhas less than |εb |πelements,
942 the set of numbers representable with radix |εb
950 |πand digits from |εD |πhas measure zero. If
958 |εD |πhas more than |εb |πelem5, 0|4|¬E|4a|¬S|4|¬W|42|¬Y,
965 |πfor |εk|4|¬R|40. |π[R. W. Graham and D. W.
973 Matula have shown that there are no more sets
982 of integer digits with these properties. And
989 Andrew Odlyzko has shown that the restriction
996 to integers is super⊗ous, in the sense that if
1005 the smallest two elements of |εD |πare 0 and
1014 1, all the digits must be integers. Proof: Let
1023 |εA|4α=↓|4|¬T(d|βk|4.|4.|4.|4d|β0)|βb|4|¬G|4d|βj|4|¬A|4D|¬Y,
1023 |πthen [0,|4|¬X)|4α=↓|4|↔w|ε|βa|β|¬A|βA|4(a|4α+↓|4S)
1026 |πand |ε(a|4α+↓|4S)|4|↔Q|4(a|¬S|4α+↓|4S) |πhas
1029 measure zero for |εa|4|=|↔6α=↓|4a|¬S|4|¬A|4A.
1033 |πWe have (0,|41)|4|↔Y|4|εS, |πand by induction
1039 on |εm |πwe will prove that |ε(m,|4m|4α+↓|41)|4|↔Y|4a|βm|4α+
1045 ↓|4S |πfor some |εa|βm. |πLet |εa|βm |πbe maximal
1053 in |εS |πwith |ε(m,|4m|4α+↓|4|≤e)|↔Q|4(a|βm|4α+↓|4S)
1057 |πof positive measure for all |ε|≤e|4|¬Q|40.
1063 |πThen |εa|βm|4|¬E|4m, |πand |εa|βm |πmust be
1069 an integer lest |εa|β|"l|βa|mm|β|"L|4α+↓|4S |πoverlap
1074 |εa|βm|4α+↓|4S |πtoo much. If |εa|βm|4|¬Q|40,
1079 |πthe fact that |εm|4α_↓|4a|βm, m|4α_↓|4a|βm|4α+↓|41)|4|↔Q|4
1083 S |πis of positive measure implies by induction
1091 that this measure is 1, and |ε(m,|4m|4α+↓|41)|4|↔Y|4a|βm|4α+
1097 ↓|4S |πsince |εS |πis closed. If |εa|βm|4α=↓|40
1104 |πand |ε(m,|4m|4α+↓|41)|4|=|↔6|↔Y|4S, |πthe maximality
1108 of |εq|βm |πshows that |εm|4|¬W|4a|ur|↔0|)m|)|4|¬W|4m|4α+↓|4
1112 1 |πfor some |εa|ur|↔0|)m|)|4|¬A|4A, |πwhere
1117 |ε(m,|4a|ur|↔0|)m|))|4|↔Y|4S; |πbut then 1|4α+↓|4|εS
1121 |πoverlaps |εa|ur|↔0|)m|)|4α+↓|4S.]|'|π!!|2If
1124 we drop the restriction 0|4|¬A|4|εD |πthere |εare
1131 |πmany other cases, some of which are quite interesting,
1140 especially the sets |¬T1, 2, 3, 4, 5, 6, 7, 8,
1151 9, 10|¬Y, |¬T1, 2, 3, 4, 5, 51, 52, 53, 54, 55|¬Y,
1163 and |¬T2, 3, 4, 5, 6, 52, 53, 54, 55, 56|¬Y.
1174 Alternatively if we allow negative digits we
1181 obtain many other solutions by the method of
1189 exercise 19, plus further sets like |¬T|→α_↓1,
1196 0, 1, 2, 3, 4, 5, 6, 7, 18|¬Y which don't meet
1208 the conditions of that exercise; it appears hopeless
1216 to _nd a nice characterization of all solutions
1224 with negative digits.]|'{A3}|≡2|≡5|≡.|9|4A positive
1229 number whose base |εb |πrepresentation has |εm
1236 |πconsectuve |ε(b|4α_↓|41)'|πs to the right of
1242 the decimal point must have the form |εc/b|gn|4α+↓|4(b|gm|4α
1249 _↓|4|≤u)/b|gn|gα+↓|gm, |πwhere 0|4|¬W|4|≤u|4|¬E|41
1252 and |εc, n |πare nonnegative integers. So if
1260 |εu/v |πhas this form, we _nd that |εb|gm|gα+↓|gnu|4α=↓|4b|g
1267 mcv|4α+↓|4b|gmv|4α_↓|4|≤uv. |πTherefore |ε|≤uv
1270 |πis an integer which is a multiple of |εb|gm.
1279 |πBut |ε0|4|¬W|4|≤uv|4|¬E|4v|4|¬W|4b|gm. |π(There
1282 can be arbitrarily long runs of other digits
1290 |εdddddddd, |πif |ε0|4|¬E|4d|4|¬W|4b|4α_↓|41,
1293 |πfor example in the representation of |εd/(b|4α_↓|41).{H11}
1299 ){H9}|'|H*?{U0}{H9L11M29}|π58320#Computer Programming!(Knuth/
folio 731 galley 2
1301 Addison-Wesley)!f. 731!Ans!g. 2c|'{A6}|≡2|≡6|≡.|9|4The
1305 proof of ``su∃ciency'' is straightforward generalization
1312 of the usual proof for base |εb, |πby successively
1321 constructing the desired representation. The
1326 proof of ``necessity'' breaks into two parts:
1333 If |ε|≤b|βn|βα↓|β1 |πis greater than |ε|¬K|βk|β|¬E|βn|4c|βk|
1338 ≤b|βk |πfor some |εn, |πthen |ε|≤b|βn|βα+↓|β1|4α_↓|4|≤e
1344 |πhas no representation for small |ε|≤e. |πIf
1351 |ε|≤b|βn|βα↓|β1|4|¬E|4|¬K|βk|β|¬E|βn|4c|βk|≤b|βk
1352 |πfor all |εn, |πbut equality does not always
1360 hold, we can show there are two representations
1368 for certain |εx. |π[See |εTransactions of the
1375 Royal Society of Canada, |πseries III, |≡4|≡6
1382 (1952), 45<55.]|'{A3}|≡2|≡7|≡.|9|4Proof by induction
1387 on |ε|¬Gn|¬G: |πIf |εn |πis even we must take
1396 |εe|β0|4|¬Q|40, |πand tahe result then follows
1402 by induction, since |εn/2 |πhas a unique such
1410 representation. If |εn |πis odd, we must take
1418 |εe|β0|4α=↓|40, |πand the problem reduces to
1424 representing |ε|→α_↓(n|4α_↓|41)/2; |πthe latter
1428 quantity is either zero or one, when there is
1437 obviously only one way to proceed, or it has
1446 a unique reversing representation by induction.|'
1452 {A3}|≡2|≡8|≡.|9|4A proof like that of exercise
1458 27 may be given. Note that |εa|4α↓|4bi |πis a
1467 multiple of |ε1|4α+↓|4i |πby a complex integer
1474 if and only if |εa|4α+↓|4b |πis even.|'{A3}|≡2|≡9|≡.|9|4It
1482 su∃ces kto prove that any collection |εT|β0,
1489 T|β1, T|β2, . . . |πsatisfying Property B may
1498 be obtained by collapsing some sollcetion |εS|β0,
1505 S|β1, S|β2, . . . , |πwhere |εS|β0|4α=↓|4|¬T0,|41,|4.|4.|4.|
1512 4,|4b|4α_↓|41|¬Y |πand all elemenats of |εS|β1,
1518 S|β2, . . . |πare multiples of |εb.|'|π!!|2To
1527 prove the latter statement, we may assume that
1535 1|4|¬A|4|εT|β0 |πand that theare is a least element
1543 |εb|4|¬Q|41 |πsuch that |εb|4|=|↔6|¬A|4T|β0.
1547 |πWe will prove, by induction on |εn, |πthat
1555 if |εnb|4|=|↔6|¬A|4T|β0, |πthen |εnb|4α↓|41,
1559 bn|4α↓|42, . . . , nb|4α↓|4b|4α_↓|41 |πare not
1567 in any of the |εT|βj|π's; but if |εnb|4|¬A|4T|β0,
1575 |πthen so are |εnb|4α+↓|41, . . . , nb|4α+↓|4b|4α_↓|41.
1584 |πThe result then follows with |εS|β1|4α=↓|4|¬Tnb|4|¬G|4nb|4
1589 |¬A|4T|β0|¬Y, S|β2|4α=↓|4T|β1, S|β3|4α=↓|4T|β2,
1592 |πetc.|'!!|2If |εnb|4|=|↔6|¬A|4T|β0, |πthen |εnb|4α=↓|4t|β0|
1596 4α+↓|4t|β1|4|¬O|4|¬O|4|¬O|4, |πwhere |εt|β1,
1599 t|β2, . . . |πare multiples of |εb; |πhence |εt|β0|4|¬W|4nb
1609 |πis a multiple of |εb. |πBy induction, |ε(t|β0|4α+↓|4k)|4α+
1616 ↓|4t|β1|4α+↓|4t|β2|4α+↓|4|¬O|4|¬O|4|¬O |πis the
1619 representation of |εnb|4α+↓|4k, |πfor 0|4|¬W|4|εk|4|¬W|4b;
1624 |πhence |εnb|4α+↓|4k|4|=|↔6|¬A|4T|βj |πfor any
1628 |εj.|'|π!!|2If |εnb|4|¬A|4T|β0 |πand 0|4|¬W|4|εk|4|¬W|4b,
1633 |πlet the representation of |εnb|4α+↓|4k |πbe
1639 |εt|β0|4α+↓|4t|β1|4α+↓|4|¬O|4|¬O|4|¬O|4. |πWe
1641 cannot have |εt|βj|4α=↓|4nb|4α+↓|4k |πfor |εj|4|¬R|41,
1646 |πlest |εnb|4α+↓|4b |πhave two representations
1651 |ε(b|4α_↓|4k)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4(nb|4α+↓|4k)|4α+↓|4|
1651 ¬O|4|¬O|4|¬O|4α=↓|4(nb)|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4b|4α+↓|4|¬
1651 O|4|¬O|4|¬O|4. |πBy induction, |εt|β0|4|πmod|4|εb|4α=↓|4k;
1655 |πand the representation |εnb|4α=↓|4(t|β0|4α_↓|4k)|4α↓|4t|β1
1658 |4α↓|4|¬O|4|¬O|4|¬O |πimplies that |εt|β0|4α=↓|4nb|4α+↓|4k.|
1661 '|π!!|2[Reference: |εNieuw Archief voor Wiskunde
1667 (3) |≡4 (1956), 15<17. |πA _nite analog of this
1676 result was derived by P. A. MacMahon, |εCombinatory
1684 Analysis |≡1 (1915), 217<223.]|'{A3}|π|≡3|≡0|≡.|9|4a)
1689 Let |εA|βj |πbe the set of numbers |εn |πwhose
1698 representation does not involve |εb|βj; |πthen
1704 by the uniqueness property, |εn|4|¬A|4A|βj |πi=
1710 |εn|4α+↓|4b|βj|4|=|↔6|¬A|4A|βj. |πConsequently
1712 |βn|4|¬A|4A|βj i= |εn|4α+↓|42b|βj|4|¬A|4A|βj.
1715 |πIt follows that, for |εj|4|=|↔6α=↓|4k, n|4|¬A|4A|βj|4|↔Q|4
1720 A|βk |πi= |εn|4α+↓|42b|βjb|βk|4|¬A|4A|βj|4|↔Q|4A|βk.
1723 |πLet |εm |πbe the number of integers |εn|4|¬A|4A|βj|4|↔Q|4A
1730 |βk |πsuch that 0|4|¬E|4|εn|4|¬W|42b|βjb|βk.
1734 |πThen there are exactly |εm |πintegers in the
1742 same range which are in |εA|βj |πbut not |εA|βk,
1751 |πexactly |εm |πin |εA|βk |πbut not |εA|βj, |πand
1759 exactly |εm |πin neither |εA|βj |πnor |εA|βk;
1766 |πhence |ε4m|4α=↓|42b|βjb|βk. |πTherefore |εb|βj
1770 |πand |εb|βk |πckan*?*?d this interval. In this
1777 range 3|4|¬M|4|→α_↓1|4|¬M|4|→α_↓2|4|¬M|46|4|¬M|48|4|¬M|42|4|
1778 ¬M|42|4|¬M|47|4|¬M|40 and 4|4|¬M|41|4|¬M|45|4|¬M|46.
1781 Thus 1|4α=↓|4|≥ |¬O 2|g0 α_↓ 13 |¬O 2|g1 α+↓
1790 7 |¬O 2|g2 α_↓ 13 |¬O 2|g3 α_↓ 13 |¬O 2|g5 α_↓
1802 13 |¬O 2|g9 α+↓ 7 |¬O 2|g1|g0.|'!!|2|εNote|*/:|\
1810 |πThe choice |εd|β0, d|β1, d|β2,|4.|4.|4.|4α=↓|45,
1815 |→α_↓3, 3, 5, |→α_↓3, 3, . . . |πalso yields
1825 a binary basis. For further details see |εMath.
1833 Comp. |≡1|≡8 (1964), 537<546; |πA. D. Sands,
1840 |εActa Mathematica, |πAcad. Sci. Hung., |≡8 (1957),
1847 65<86.|'{A3}|≡3|≡1|≡.|9|4(See also the related
1852 exercises 3.2.2<11, 4.3.2<13, 4.6.2<22.)|'!!|2a)|9By
1857 multiplying numerator andffd*?*?*?!!|2a)|9By multiplying
1861 numerator and denominator by suitable powers
1867 of 2, we may assume that |εu|4α=↓|4(.|4.|4.|4u|β2u|β1u|β0)|β
1873 2 |πand |εv|4α=↓|4(.|4.|4.|4v|β2v|β1v|β0)|β2,
1876 |πwhere |εv|β0|4α=↓|41. |πThe following computational
1881 method now determines |εw, |πusing the notation
1888 |εu|g(|gn|g) |πto stand for the integer |ε(u|βn|βα_↓|β1|4.|4
1894 .|4.|4u|β0)|β2|4α=↓|4u|4|πmod|4|ε2|gn |πwhen
1896 |εn|4|¬Q|40:|'|π!!|2Let |εw|β0|4α=↓|4u|β0. |πFor
1900 |εn|4α=↓|41, 2, . . . , |πassume that we have
1910 found an integer |εw|g(|gn|g)|4α=↓|4|ε(w|βn|βα_↓|β1|4.|4.|4.
1913 |4w|β0)|β2 |πsuch that |εu|g(|gn|g)|4|"o|4v|g(|gn|g)w|g(|gn|
1916 g) |π(modulo 2|ε|gn). |πThen |εu|g(|gn|gα+↓|g1|g)*444*?*?|4α=↓|
1920 4u|β0. |πFor |εn|4α=↓|41, 2, . . . , |πassume
1929 that we have found an integer |εw|g(|gn|g)|4α=↓|4|ε(w|βn|βα_
1935 ↓|β1|4.|4.|4.|4w|β0)|β2 |πsuch that |εu|g(|gn|g)|4|"o|4v|g(|
1938 gn|g)w|g(|gn|g) |π(modulo 2|ε|gn). |πThen |εu|g(|gn|gα+↓|g1|
1942 g)|4|"o|4v|g(|gn|gα+↓|g1|g)w|g(|gn|g) |π(modulo
1944 2|ε|gn), |πhence we may let |εw|βn|4α=↓|40 |πor
1951 1 according as |ε(u|g(|gn|gα+↓|g1|g)|4α_↓|4v|g(|gn|gα+↓|g1|g
1954 )w|g(|gn|g)|π)mod|42|ε|gn|gα+↓|g1 |πis 0 or |ε2|gn.|'
1959 !!|2|πb)|9Find the smallest integer |εk |πsuch
1965 that |ε2|gk|4|"o|41 |π(modulo |ε2n|4α+↓|41).
1969 |πThen |ε1/(2n|4α+↓|41)|4α=↓|4m/(2|gk|4α_↓|41)
1971 |πfor some integer |εm, 1|4|¬E|4m|4|¬W|42|gk|gα_↓|g1.
1976 |πLet |ε|≤a |πbe the |εk-|πbit binary representation
1983 of |εm; |πthen |ε(0.|≤a|≤a|≤a|4.|4.|4.)|β2 |πtimes
1988 |ε2n|4α+↓|41 |πis (0.111|4.|4.|4.)|β2|4α=↓|41
1991 |πin the binary system, and (.|4.|4.|4|ε|≤a|≤a|≤a)|β2
1997 |πtimes |ε2n|4α+↓|41 |πis (.|4.|4.|4111)|β2|4α=↓|4|→α_↓1
2001 in the 2-adic system.|'!!|2c)|9If |εu |πis rational,
2009 say |εu|4α=↓|4m/2|gtn |πwhere |εn |πis odd and
2016 positive, the 2-adic representation of |εu |πis
2023 periodic, because the set of numbers with periodic
2031 expansions includes |→α_↓1/|εn |πand is closed
2037 under the operations of negation, division by
2044 2, and addition.|'!!|2d)|9The square of any number
2052 of the form (.|4.|4.|4|εu|β2u|β11)|β2 |πhas the
2058 form (.|4.|4.|4001)|β2, hence the condition is
2064 necessary. To show the su∃ciency, use the following
2072 procedure to compute |εv|4α=↓|4{H10}|¬H{H9}|v4n|)
2076 |πwhen |εn |πmod|48|4α=↓|41:|'{A3}{I3.2H}!!|2|≡H|≡1|≡.|9Set
2080 |εn|4|¬L|4(n|4α_↓|41)/8, k|4|¬L|42, v|β0|4|¬L|41,
2083 v|β1|4|¬L|40, v|4|¬L|41.|'{A3}|π!!|2|≡H|≡2|≡.|9If
2086 |εn |πis even, set |εv|βk|4|¬L|40, n|4|¬L|4n/2.
2092 |πOtherwise set |εv|βk|4|¬L|41, n|4|¬L|4(n|4α_↓|4v|4α_↓|42|g
2095 k|gα_↓|g1)/2, v|4|¬L|4v|4α+↓|42|gk.|'!!|2|π|≡H|≡3|≡.|9Increa
2097 se |εk |πby 1 and return to H2.|'{A3}{IC}|≡3|≡2|≡.|9|4A
2106 generalization appears in |εMath. Comp. |≡2|≡9
2112 (1975), 84<86.|'{A25}{H10L12}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.
2114 |∨2|∨.|∨1|'{A11}{H9L11}|9|1|≡1|≡.|9|4|εN|4α=↓|4(62,
2116 |→α+↓.60|422|452|400); h|4α=↓|4(37,|4|→α+↓.10|454|450|400).
2118 |πNote that 10|εh |πwould be (38,|4|→α+↓.01|405|445|400).|'
2124 {A3}|9|1|≡2|≡.|9|4|εb|gE|gα_↓|gq(1|4α_↓|4b|gα_↓|gp),
2125 b|gα_↓|gq|gα_↓|gp; b|gE|gα_↓|gq(1|4α_↓|4b|gα_↓|gp),
2127 b|gα_↓|gq|gα_↓|g1.|'{A3}|π|9|1|≡3|≡.|9|4When
2129 |εe |πdoes not have its smallest value, the most
2138 signi_cant ``one'' bit (which appears in all
2145 such normalized numbers) need not appear in the
2153 computer word. [This idea appeared in Zuse's
2160 machine in 1936.]|'|9|1|≡4|≡.|9|4(51, |→α+↓.10209877);
2165 (50,|4|→α+↓.12346000); (53,|4|→α+↓.99999999).
2167 The third answer would be (54,|4|→α+↓.10000000)
2173 if the _rst operand had been (45,|4|→α_↓.50000000).|'
2180 {A3}|9|1|≡5|≡.|9|4If |εx|4|¬Z|4y |πand |εm |πis
2185 an integer then |εmb|4α+↓|4x|4|¬Z|4mb|4α+↓|4y.
2189 |πAnother crucial property is that |εx/b |πand
2196 |εy/b |πwill round to the same integer, whenever
2204 |εx|4|¬Z|4y.|'!!|2|πNow if |εb|gα_↓|gp|gα_↓|g2F|βv|4|=|↔6α=↓
2207 |4f|βv |πwe must have |ε(b|gp|gα+↓|g2fv)|πmod|4|εb|4|=|↔6α=↓
2211 |40; |πhence the transformation leaves |εf|βv
2217 |πunchanged unless |εe|βu|4α_↓|4e|βv|4|¬R|42.
2220 |πSince |εu |πwas normalized, it is nonzero and
2228 |ε|¬Gf|βu|4α+↓|4f|βv|¬G|4|¬Q|4b|gα_↓|g1|4α_↓|4b|gα_↓|g2|4|¬R
2228 |4b|gα_↓|g2: |πthe leading nonzero digit of |εf|βu|4α+↓|4f|β
2234 v |πmust be at most two places to the right of
2245 the radix point, and the rounding operation will
2253 convert |εb|gp|gα+↓|gj(f|βu|4α+↓|4f|βv) |πto
2256 an integer, where |εj|4|¬E|41. |πThe proof will
2263 be complete if we can show that |εb|gp|gα+↓|gj|gα+↓|g1()f|βu
2270 |4α+↓|4f|βv)|4|¬Z|4b|gp|gα+↓|gj|gα+↓|g1(f|βu|4α+↓|4b|gα_↓|gp
2270 |gα_↓|g2F|βv). |πBy the previous paragraph, we
2276 have |εb|gp|gα+↓|g2(f|βu|4α+↓|4f|βv)|4|¬Z|4b|gp|gα+↓|g2f|βu|
2277 4α+↓|4F|βv|4α=↓|4b|gp|gα+↓|g2(f|βu|4α+↓|4b|gα_↓|gp|gα_↓|g2F|
2277 βv), |πwhich implies the desired result for all
2285 |εj|4|¬E|41.|'!!|2|πNote that, when |εb|4|¬Q|42
2290 |πis even, such an integer |εF|βv |πalways exists;
2298 but when |εb|4α=↓|42 |πwe require |εp|4α+↓|43
2304 |πbits (let |ε2F|βv |πbe an integer). When |εb
2312 |πis odd, an integer |εF|βv |πalways exists except
2320 in the case of division, when a remainder of
2329 |ε|f1|d32|)b |πis possible.|'{A3}|9|1|≡6|≡.|9|4(Consider
2333 the case |εe|βu|4α=↓|4e|βv, f|βu|4α=↓|4|→α_↓f|βv
2337 |πin Program A.) Register A retains its previous
2345 sign, as in |¬a|¬d|¬d.|'{A3}|9|1|≡7|≡.|9|4Say
2350 that a number is normalized i= it is zero or
2360 its fraction part satis_es |f1|d36|)|4|¬W|4|¬G|εf|¬G|4|¬W|4|
2364 f1|d32|). |πA |ε(p|4α+↓|41)-|πplace accumulator
2368 su∃ces for addition and subtraction; rounding
2374 (except during division) is equivalent to truncation.
2381 A very pleasant system indeed*3 We might represent
2389 numbers with excess-zero exponent, inserted between
2395 the _rst and subsequent digits of the fraction,
2403 and complemented if the fraction is negative,
2410 so that _xed-point order is preserved.|'{A3}|9|1|≡8|≡.|9|4(a
2416 ) (06, |→α+↓.12345679)|4|↔V|4(06,|4|→α_↓.12345678),
2419 (01,|4|→α+↓.10345678)|4|↔V|4(00, |→α_↓.94000000);
2421 (b) (99, |→α+↓.87654321)|4|↔V|4itself, (99, |→α+↓.99999999)|
2425 4|↔V|4(91, |→α+↓.50000000).|'{A3}|9|1|≡9|≡.|9|4|εa|4α=↓|4(|→
2427 α_↓50, |→α+↓.10000000), b|4α=↓|4(|→α_↓41, |→α+↓.20000000),
2431 c|4α=↓|4a, d|4α=↓|4(|→α_↓41, |→α+↓.80000000),
2434 y|4α=↓|4(11, |→α+↓.10000000).|'{A3}|π|≡1|≡0|≡.|9|4(50,|4|→α+
2436 ↓.99999000)|4|↔V|4(55,|4|→α+↓.99999000).|'|Hβ*?*?*?*?{U0}{H9L11M
folio 735 galley 3
2437 29}|π58320#Computer Programming!(Knuth/Addison-Wesley)!f.
2439 735!Ans!g. 3c|'{A6}|≡1|≡1|≡.|9|4(50,|4|→α+↓.10000001)|4|↔V|4
2441 (50,|4|→α+↓.99999990).|'{A3}|≡1|≡2|≡.|9|4If 0|4|¬W|4|ε|¬Gf|β
2443 u|¬G|4|¬W|4|¬Gf|βv|¬G, |πthen |ε|¬Gf|βu|¬G|4|¬E|4|¬Gf|βv|¬G|
2445 4α_↓|4b|gα_↓|gp; |πhence |ε1/b|4|¬W|4|¬Gf|βu/f|βv|¬G|4|¬E|41
2447 |4α_↓|4b|gα_↓|gp/|¬Gf|βv|¬G|4|¬W|41|4α_↓|4b|gα_↓|gp.
2448 |πIf 0|4|¬W|4|¬Gf|βv|¬G|4|¬E|4|¬Gf|βu|¬G, |πwe
2451 have |ε1/b|4|¬W|4|¬Gf|βu/f|βv|¬G/b|4|¬E|4(1|4α_↓|4b|gα_↓|gp)
2452 /(1/b)/b|4α=↓|41|4α_↓|4b|gα_↓|gp.|'{A3}|π|≡1|≡3|≡.|9|4See
2454 J. Michael Yohe, |εIEEE Transactions |π|≡C|≡-|≡2|≡2
2460 (1973), 577<586.|'{A3}|≡1|≡4|≡.|9|4|∂|¬f|¬i|¬x!|∂|¬s|¬t|¬j|9
2462 |3!|∂|¬9|¬f!!!!|9|3|∂Float-to-_x subroutine:|'
2464 |L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬1|L|¬t|¬e|¬m|¬p|≤#|¬
2465 e|¬x|¬p|≤&|LrI1|4|¬L|4|εe.>|π|L|L|¬s|¬l|¬a|L|¬1|LrA|4|¬L|4|→
2466 |¬N|εf|1f|1f|1f|10.>|L|L|¬j|¬a|¬z|L|¬9|¬f|L|πIs
2468 input zero?>|L|L|¬d|¬e|¬c|¬1|L|¬1>|L|L|¬c|¬m|¬p|¬a|L|≤$|¬0|≤
2471 $|≤#|¬1|¬.|¬1|≤&|LIf leading byte is zero,>|L|L|¬j|¬e|Lα/↓|≤
2476 */|¬4|L!shift left again.>|L|L|¬e|¬n|¬n|¬1|L|≤*/|¬q|≤*/|¬4|¬,|¬
2479 1>|L|L|¬j|¬1|¬n|L|¬f|¬i|¬x|¬o|¬v|¬f|¬l|¬o|LIs
2481 magnitude too large?>|L|L|¬e|¬n|¬t|¬x|L|¬0>|L|L|¬s|¬r|¬a|¬x|
2485 L|¬0|¬,|¬1>|L|L|¬c|¬m|¬p|¬x|L|≤$|¬1/|2/|¬2|≤$>
2487 |L|L|¬j|¬l|L|¬9|¬f>|L|L|¬j|¬g|Lα/↓|≤%|¬2>|L|L|¬j|¬a|¬o|L|¬9|
2489 ¬f>|L|L|¬s|¬t|¬a|Lα/↓|≤%|¬1|≤#|¬0|¬;|¬0|≤&|LRound,
2491 if necessary.>|L|L|¬i|¬n|¬c|¬a|L|¬1|LAdd |→|¬N1
2495 (over⊗ow is impossible).>|L|¬9|¬h|L|¬j|¬m|¬p|Lα/↓|LExit
2499 from subroutine.>{A3}|≡1|≡5|≡.|9|4|∂|¬F|¬P|9|3|∂|¬s|¬t|¬j|9|
2501 3|∂|¬e|¬x|¬i|¬t|¬f!!!!!!|∂Fractional part subroutine:|'
2504 |L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|LEnsure over⊗ow is
2507 o=.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p|L|¬t|¬e|¬m|¬¬*?*?*?¬s|¬t|¬a|L|¬
2508 t|¬e|¬m|¬p|L|¬t|¬e|¬m|¬p|4|¬L|4|εu.>|L|L|π|¬e|¬n|¬t|¬x|L|¬0>
2510 |L|L|¬s|¬l|¬a|L|¬1|LrA|4|¬L|4|εf|βu.>|L|L|¬l|¬d|¬s|L|¬t|¬e|¬
2511 m|¬p|≤#|¬e|¬x|¬p|≤&|L|πrI2|4|¬L|4|εe|βu.>|L|L|π|¬d|¬e|¬c|¬2|
2512 L|¬q>|L|L|¬j|¬2|¬n|¬p|Lα/↓|≤%|¬3>|L|L|¬s|¬l|¬a|L|¬0|¬,|¬2|LR
2514 emove integer part of |εu.>|L|L|π|¬e|¬n|¬t|¬2|L|¬0>
2520 |L|L|¬j|¬a|¬n|¬n|L|¬1|¬f>|L|L|¬e|¬n|¬n|¬2|L|¬0|¬,|¬2|LFracti
2521 on is negative: _nd>|L|L|¬s|¬r|¬a|¬x|L|¬0|¬,|¬2|L!its
2526 complement.>|L|L|¬e|¬n|¬t|¬2|L|¬0>|L|L|¬j|¬a|¬z|Lα/↓|≤%|¬2>
2529 |L|L|¬i|¬n|¬c|¬a|L|¬1>|L|L|¬a|¬d|¬d|L|¬w|¬m|¬1|LAdd
2531 word size minus one.>|L|¬1|¬h|L|¬i|¬n|¬c|¬2|L|¬q|LPrepare
2536 to normalize the answer.>|L|L|¬j|¬m|¬p|L|¬n|¬o|¬r|¬m|LNormal
2540 ize, round, and exit.>|L|¬8|¬h|L|¬e|¬q|¬u|L|¬1|≤#|¬1|¬.|¬1|≤
2544 &>|L|¬w|¬m|¬1|L|¬c|¬o|¬n|L|¬8|¬b|≤*/|¬1|¬,|¬8|¬b|≤*/|¬1|≤#|¬1|
2545 ¬.|¬4|≤&|LWord size minus one>{A3}|≡1|≡6|≡.|9|4If
2550 |ε|¬Gc|¬G|4|¬R|4|¬Gd|¬G, |πthen set |εr|4|¬L|4d|4|↔n|4c,
2554 s|4|¬L|4c|4|↔V (r|4|↔N|4d); x|4|¬L|4{H11}({H9}a|4|↔V|4(b|4|↔
2556 N|4r){H11}){H9}|4|↔n|4s; y|4|¬L|4{H11}({H9}b|4|↔B|4(a|4|↔N|4
2557 r){H11}){H9}|4|↔n|4s. |πOtherwise set |εr|4|¬L|4c|4|↔n|4d,
2561 s|4|¬L|4d|4|↔V|4(r|4|↔N|4c); x|4|¬L|4{H11}({H9}(a|4|↔N|4r)|4
2562 |↔V|4b{H11}){H9}|4|↔n|4s, y|4|¬L|4{H11}({H9}(b|4|↔N|4r)|4|↔B
2563 |4a{H11}){H9}|4|↔n|4s. |πThen |εx|4α+↓|4iy |πis
2567 the desired approximation to |ε(a|4α+↓|4bi)/(c|4α+↓|4di).
2572 [CACM |≡5 (1963), 435.] |πOther algorithms for
2579 complex arithmetic and function evaluation are
2585 given by P. Wynn, |εBIT |≡2 (1962), 232<255;
2593 |πsee also Paul Friedland, |εCACM |≡1|≡0 (1967),
2600 665.|'{A3}|π|≡1|≡7|≡.|9|4See Robert Morris, |εIEEE
2605 Transactions |π|≡C|≡-|≡2|≡0 (1971), 1578<1579.
2609 Error analysis is more di∃cult with such systems,
2617 so internal arithmetic is correspondingly more
2623 desirable.|'{A3}|≡1|≡8|≡.|9|4For positive numbers:
2627 shift fraction left until |εf|β1|4α=↓|41, |πthen
2633 round, then if the fraction is zero (rounding
2641 over⊗ow) shift it right again. For negative numbers:
2649 shift fraction left until |εf|β1|4α=↓|40, |πthen
2655 round, then if the fraction is zero (rounding
2663 under⊗ow) shift it right again.|'{A3}|≡1|≡9|≡.|9|4{H11}({H9}
2668 43|4α+↓|4(1 if |εe|βv|4|¬W|4e|βu)|4α_↓|4(1 |πif
2672 fraction over⊗ow)|4α_↓N4(*?*?{A3}|≡1|≡9|≡.|9|4{H11}({H9}43|4α+
2673 ↓|4(1 if |εe|βv|4|¬W|4e|βu)|4α_↓|4(1 |πif fraction
2678 over⊗ow)|4α_↓|4(10 if result zero)|4α+↓|4(4 if
2683 magnitude is rounded up)|4α+↓|4(1 if _rst rounding
2690 digit is |εb/2)|4α+↓|4(5 |πif rounding digits
2696 are |εW|β2|40|4.|4.|4.|40)|4α+↓|4(7 |πif rounding
2700 over⊗ow)|4α+↓|47|εN|4α+↓|4A(|→α_↓1|4α+↓|4(11
2701 |πif |εN|4|¬Q|40)){H11}){H9}u, |πwhere |εN |πis
2706 the number of left shifts during normalization,
2713 |εA|4α=↓|41 |πif rX receives nonzero digits (otherwise
2720 |εA|4α=↓|40). |πThe maximum time of |ε73u |πoccurs
2727 for example when |εu|4α=↓|4↓α+↓50|401|400|400|400,
2731 v|4α=↓|4|→α_↓46|449|499|499|499, b|4α=↓|4100.
2733 |π[The average time, considering the statistical
2739 data in Section 4.2.4, will be about 45|f1|d32|)|εu.]|'
2747 {A3}{A22}{H10L12}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨2|∨.|∨2|'
2748 {A11}{H9L11}|9|1|≡1|≡.|9|4|εu|4|↔B|4v|4α=↓|4u|4|↔V|4|→α_↓v|4
2748 α=↓|4|→α_↓v|4|↔V|4u|4α=↓|4|→α_↓(v|4|↔V|4|→α_↓u)|4α=↓|4|→α_↓(
2748 v|4|↔B|4u).|'{A3}|9|1|≡2|≡.|9|4u|4|↔V|4x|4|¬R|4u|4|↔V|40|4α=
2749 ↓|4u, |πby (8), (2), (6); hence by (8) again,
2758 |ε(u|4|↔V|4x)|4|↔V|4v|4|¬R|4u|4|↔V|4v. |πSimilarly,
2760 (8) and (6) together with (2) imply that |ε(u|4|↔V|4x)|4|↔V|
2768 4(v|4|↔V|4y)|4|¬R|4(u|4|↔V|4x)|4|↔V|4v.|'{A3}|π|9|1|≡3|≡.|9|
2769 4|εu|4α=↓|48.0000001, v|4α=↓|41.2500008, w|4α=↓|48.0000008;
2772 (u|4|↔N|4v)|4|↔N|4w|4α=↓|480.000064, u|4|↔N|4(v|4|↔N|4w)α=↓|
2773 480.000057.|'{A3}|π|9|1|≡4|≡.|9|4Yes, let 1/|εu|4|¬V|4v|4α=↓
2776 |4w |πwhere |εv |πis large.|'{A3}|9|1|≡5|≡.|9|4Not
2782 always; in decimal arithmetic take |εu|4α=↓|4v|4α=↓|49.|'
2788 {A3}|π|9|1|≡6|≡.|9|4(a) Yes. (b) Only for |εb|4α+↓|4p|4|¬E|4
2793 4 |π(try |εu|4α=↓|41|4α_↓|4b|gα_↓|gp). |π[W.
2797 M. Kahar observes that the identity |εdoes |πhold
2805 whenever |εb|gα_↓|g1|4|¬E|4f|βu|4|¬E|4b|gα_↓|g1|g/|g2.
2807 |πIt follows that 1|4|↔n|4{H11}({H9}1|4|↔n|4(1|4|↔n|4|εu){H1
2810 1}){H9}|4α=↓|41|4|↔n|4|εu |πfor all |εu.]|'{A3}|9|1|≡7|≡.|9|
2814 4|πIf |εu |πand |εv |πare consecutive ⊗oating-binary
2821 numbers, |εu|4|↔V|4v|4α=↓|42u |πor |ε2v. |πWhen
2826 it is |ε2v |πwe often ha¬e |εu|=|g|*2`|g2|4|↔V|4v|=|g|*2`|g2|4
2832 |¬W|42v|=|g|*2`|g2. |πFor example, |εu|4α=↓|4.10|4.|4.|4.|400
2835 1, v|4α=↓|4.10|4.|4.|4.|4010, u|4|↔V|4v|4α=↓|42v,
2838 u|=|g|*2`|g2|4|↔V|4v|=|g|*2`|g2|4α=↓|4.10|4.|4.|4.|4011.|'
2839 {A3}|π|9|1|≡8|≡.|9|4(a) |→|¬Z, |→|¬V; (b) |→|¬Z,
2844 |→|¬V; (c) |→|¬Z, |→|¬¬ (d) |→|¬Z; (e) |→|¬Z.|'
2852 {A3}|9|1|≡9|≡.|9|4|ε|¬Gu|4α_↓|4w|¬G|4|¬E|4|¬Gu|4α_↓|4v|¬G|4α
2852 +↓|4|¬Gv|4α_↓|4w|¬G |¬E |≤e|β1 |πmin|ε(b|ge|ru|gα_↓|gq,
2856 b|βe|mv|βα_↓|βq)|4α+↓|4|≤e|β2 |πmin|ε(b|βe|mv|βα_↓|βq,
2858 b|βe|mw|βα_↓|βq) |¬E |≤e|β1b|βe|mu|gα_↓|gq|4α↓|4|≤e|β2b|ge|r
2860 w|gα_↓|gq |¬E (|≤e|β1 α+↓ |≤e|β2)|πmax|ε(b|ge|ru|gα_↓|gq,
2865 c|ge|rw|gα_↓|gq). |πThe result cannot be strengthened
2871 in general, since for example we might have |εe|βu
2880 |πvery small compared to both |εe|βv |πand |εe|βw,
2888 |πand this means |εu|4α_↓|4w |πmight be fairly
2895 large under kthe hypotheses.|'{A3}|≡1|≡0|≡.|9|4If
2900 |εb|4|¬Q|42, |πwe have |ε.a|β1|4.|4.|4.|4a|βp|βα_↓|β1a|βp|4|
2903 ↔N|4.9|4.|4.|4.|499|4α=↓|4.a|β1|4.|4.|4.|4a|βp|βα_↓|β1(a|βp|
2903 4α_↓|41) |πif we take |εa|βp|4|¬R|42; |πhere
2909 ``9'' stands for |εb|4α_↓|41. |πFurthermore,
2914 |ε.a|β1|4.|4.|4.|4a|βp|βα_↓|β1a|βp|4|↔N|41.0|4.|4.|4.|40|4α=
2914 ↓|4.a|β1|4.|4.|4.|4a|βp|βα_↓|β10, |πso the multiplication
2918 is not monotone. But when |εb|4α=↓|42, |πthis
2925 argument can be extended to show that multiplication
2933 |εis |πmonotone; obviously the ``certain computer''
2939 had |εb|4|¬Q|42.|'{A3}|π|≡1|≡1|≡.|9|4Without
2942 loss of generality, let |εx |πbe an integer,
2950 |ε|¬Gx|¬G|4|¬W|4b|gp. |πIf |εe|4|¬E|40 |πthen
2954 |εt|4α=↓|40. |πIf |ε0|4|¬W|4e|4|¬E|4p |πthen
2958 |εx|4α_↓|4t |πhas at most |εp|4α+↓|41 |πdigits,
2964 the least signi_cant being zero. If |εe|4|¬Q|4p
2971 |πthen |εx|4α_↓|4t|4α=↓|40. |π[The result holds
2976 also under the weaker hypothesis |ε|¬Gt|¬G|4|¬W|42b|ge.]|'
2982 {A3}|π|≡1|≡2|≡.|9|4Assume that |εe|βu|4α=↓|4p,
2985 e|βv|4|¬E|40, u|4|¬Q|40. |πCase 1, |εu|4|¬Q|4b|gp|gα_↓|g1.
2990 |πCase (1b), |εw|4α=↓|4u, |¬Gv|¬G|4|¬E|4|f1|d32|).
2994 |πThen |εu|¬S|4α=↓|4u, v|¬S|4α=↓|40, u|¬C|4α=↓|4u,
2998 v|¬C|4α=↓|40. |πIf |ε|¬Gv|¬G|4α=↓|4|f1|d32|)
3001 |πand more general rounding is permitted we might
3009 also have |εu|¬S|4α=↓|4u|4|¬N1. |πCase (1c),
3014 |εw|4α=↓|4u|4α_↓|41, v|4|¬E|4|→α_↓|f1|d32|),
3016 e|βv|4α=↓|40. |πThen |εu|¬S|4α=↓|4u |πor |εu|4α_↓|41,
3021 v|¬S|4α=↓|4|→α_↓1, u|¬C|4α=↓|4u, v|¬C|4α=↓|4|→α_↓1
3024 |πor 0. Case 2, |εu|4α=↓|4b|gp|gα_↓|g1. |πCase
3030 (2a), |εw|4α=↓|4u|4α+↓|41, v|4|¬R|4|f1|d32|),
3033 e|βv|4α=↓|40. |πLike (1a). Case (2b), |εw|4α=↓|4u,
3039 |¬Gv|¬G|4|¬e|4|f1|d32|), u|¬S|4|¬R|4u. |πLike
3042 (1b). Case (2c), |εw|4α=↓|4u, |¬Gv|¬G|4|¬E|4|f1|d32|),
3047 u|¬S|4|¬W|4u. |πThen |εu|¬S|4α=↓|4u|4α_↓|4j/b
3050 |πwhere |εv|4α=↓|4j/b|4α+↓|4v|β1 |πand |ε|¬Gv|β1|¬G|4|¬E|4|f
3053 1|d32b|gα_↓|g1 |πfor some positive integer |εj|4|¬E|4|f1|d32
3058 |)b; |πwe have |εv|¬S|4α=↓|40, u|¬C|4α=↓|4u,
3063 v|¬C|4α=↓|4j/b. |πCase (2d), |εw|4|¬W|4u. |πThen
3068 |εw|4α=↓|4u|4α_↓|4j/b |πwhere |εv|4α=↓|4|→α_↓j/b|4α+↓|4v|β1
3071 |πand |ε|¬Gv|β1|¬G|4|¬E|4|f1|d32|)b|gα_↓|g1 |πfor
3074 some positive integer |εj|4|¬E|4b; |πwe have
3080 |ε(v|¬S,|4u|¬C)|4α=↓|4(|→α_↓j/b,|4u), |πand |ε(u|¬S,|4v|¬C)|
3082 4α=↓|4(u,|4|→α_↓j/b) |πor |ε(u|4α_↓|41/b, (1|4α_↓|4j)/b{H11}
3085 ){H9}, |πthe latter case only when |εv|β1|4α=↓|4|f1|d32|)b|g
3091 α_↓|g1. |πIn all cases |εu|4|↔B|4u|¬S|4α=↓|4u|4α_↓|4u|¬S,
3096 v|4|↔B|4v|¬S|4α=↓|4v|4α_↓|4v|¬S, u|4|↔B|4u|¬S|4α=↓|4u|4α_↓|4
3097 u|¬C, v|4|↔B|4v|¬C|4α=↓|4v|4α_↓|4v|¬C, |πround|ε(w|4α_↓|4u|4
3099 α_↓|4v)|4α=↓|4w|4α_↓|4u|4α_↓|4v.|'{A3}|π|≡1|≡3|≡.|9|4Since
3101 round|ε(x)|4α=↓|40 |πi= |εx|4α=↓|40, |πwe want
3106 to determine which integers |εm, n |πhave the
3114 property that |εm|4|↔n|4n |πis an integer i=
3121 |εm/n |πis. |πAssume that |ε|¬Gm|¬G, |¬Gn|¬G|4|¬W|4b|gp.
3127 |πIf |εm/n |πis an integer then |εm|4|↔n|4n|4α=↓|4m/n
3134 |πis also. Conversely if |εm/n |πis not an integer,
3143 but |εm|↔nn |πis, we have |ε1/|¬Gn|¬G|4|¬E|4|¬Gm|↔nn|4α_↓|4m
3148 /n|¬G|4|¬E|4|f1|d32|)|4|¬Gm/n|¬G|4b|g1|gα_↓|gp,
3149 |πhence |ε|¬Gm|¬G|4|¬R|42b|gp|gα_↓|g1. |πOur
3152 answer is therefore to require |ε|¬Gm|¬G|4|¬W|42b|gp|gα_↓|g1
3157 |πand |ε0|4|¬W|4|¬Gn|¬G|4|¬W|4b|gp. |π(Slightly
3161 weaker hypotheses are also possible.)|'{A3}|π|≡1|≡4|≡.|9|4|ε
3166 |¬G(u |↔N v) |↔N w α_↓ uvw|¬G |¬E |¬G(u |↔N v)
3177 |↔N w α_↓ (u |↔N v)w|¬G α+↓ |¬Gw|¬G |¬Gu |↔N
3187 v α_↓ uv|¬G |¬E |≤d|β(|βu|β|↔N|βv|β)|β|↔N|βw
3192 α+↓ b|ge|rw|gα_↓|gq|gα_↓|g1|rw|≤d|βu|β|↔N|βv
3194 |¬E (1 α+↓ b)|4|≤d|β(|βu|β|↔N|βv|β)|β|↔N|βw.
3198 |πNow |ε|¬Ge|β(|βu|β|↔N|βv|β)|β|↔N|βw α_↓ e|βu|β|↔N|β(|βv|β|
3201 ↔N|βw|¬G |¬E 2, |πso we may take |ε|≤e α=↓ |f1|d32|)(1
3211 α+↓ b)b|g2|gα_↓|gp.|'{A3}|π|≡1|≡5|≡.|9|4|εu|4|¬E|4v
3214 |πimplies that |ε(u|4|↔V|4u)|4|↔n|42|4|¬E|4(u|4|↔V|4v)|4|↔n|
3216 42|4|¬E|4(v|4|↔V|4v)|4|↔n|42, |πso the condition
3220 holds for all |εu |πand |εv |πi= it holds whenever
3230 |εu|4α=↓|4v. |πFor base |εb|4α=↓|42, |πthe condition
3236 is therefore always satis_ed (barring over⊗ow);
3242 but for |εb|4|¬Q|42 |πthere are numbers |εv|4|=|↔6α=↓|4w
3249 |πsuch that |εv|4|↔V|4v|4α=↓|4w|4|↔V|4w, |πhence
3253 the condition fails. [On the other hand, the
3261 formula |εu|4|↔V|4{H11}({H9}(v|4|↔B|4u)|4|↔n|42{H11}){H9}
3263 |πdoes give a midpoint in the correct range.
3271 |εProof|*/:|\ |πIt su∃ces to show that |εu|4α+↓|4(v|4|↔B|4u)|
3277 4|↔n|42|4|¬E|4v, |πi.e., |ε(v|4|↔B|4u)|4|↔n|42|4|¬E|4v|4α_↓|
3279 4u; |πand it is easy to verify that round{H11}({H9}|f1|d32|)
3287 round|ε(x){H11}){H9}|4|¬E|4x |πfor all |εx|4|¬R|40.]|'
3292 {A3}|π|≡1|≡6|≡.|9|4(a) Exponent changes occur
3296 at |¬K|β1|β0|4α=↓|411.111111, |¬K|β9|β1|4α=↓|4101.11111,
3299 |¬K|β9|β0|β1|4α=↓|41001.1102, |¬K|β9|β0|β0|β1|4α=↓|410001.02
3300 0, |¬K|β9|β0|β0|β0|β9|4α=↓|4100000.91, |¬K|β9|β0|β0|β8|β1|β9
3302 |4α=↓|41000000.0; |¬K|β1|β0|β0|β0|β0|β0|β0|4α=↓|41109099.1.
3304 (b) |¬K|ε|β1|β|¬E|βk|β|¬E|βn|41.2345679|4α=↓|41224782.1,
3306 |πand (14) tries to take the square root of |→α_↓.0053187053
3315 . But (15) and (16) are exact in this case. [If
3326 |εx|βk|4α=↓|41|4α+↓|4|"l(k|4α_↓|41)/2|"L10|gα_↓|g7,
3327 |π(15) and (16) have errors of order |εn.] (c)
3336 |πBasically we need to show that |εu|4|↔V|4(v|4|↔B|4u)|4|↔n|
3342 4k |πlies between |εu |πand |εv; |πsee exercise
3350 15.|'{A3}|h|≡1|≡7|≡.|9|4|∂|¬f|¬c|¬m|¬p!|∂|¬c|¬m|¬p|¬a!|∂|≡e|
3351 ≡p|≡s|≡i|≡l|≡o|≡n|≤#|¬1|¬.|¬5|≤&!!|∂Make rA nonzero
3354 with same sign.|E|n|'|≡1|≡7|≡.|9|4|L|¬f|¬c|¬m|¬p|L|¬s|¬t|¬j|
3357 L|¬9|¬f|LFloating point comparison subroutine:>
3361 |L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|LEnsure over⊗ow is
3364 o=.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬a|¬n|L|¬t|¬e|¬m|
3366 ¬p|L|εv|4|¬L|4|→α_↓v.|π>!|9|7(Copy here lines
3370 07-20 of Program 4.2.1A.)|'|L|L|¬l|¬d|¬x|L|¬f|¬v|≤#|¬0|¬.|¬0
3374 |≤&|LSet rX to zero with sign of |εf|βv.|π>|L|L|¬d|¬e|¬c|¬1|
3382 L|¬5>|¬j|¬1|¬n|Lα/↓|≤%|¬2>|L|L|¬e|¬n|¬t|¬1|L|¬0|LReplace
3385 large di=erence in exponents>|L|L|¬s|¬r|¬a|¬x|L|¬5|¬,|¬1|L!b
3389 y a smaller one.>|L|L|¬a|¬d|¬d|L|¬f|¬u|LrA|4|¬L|4di=erence
3394 of operands.>|L|L|¬j|¬o|¬v|L|¬7|¬f|LFraction
3397 over⊗ow: not |→|¬Z.>|L|L|¬c|¬m|¬p|¬a|L|¬e|¬p|¬s|¬i|¬l|¬o|¬n|
3400 ≤#|¬1|¬.|¬5|≤&>|L|L|¬j|¬g|L|¬8|¬f|LJump if not
3404 |→|¬Z.>|L|L|¬j|¬l|L|¬6|¬f|LJump if |→|¬Z.>|L|L|¬j|¬x|¬z|L|¬9
3408 |¬f|LJump if |→|¬Z.>|L|L|¬j|¬x|¬p|L|¬1|¬f|LIf
3412 |¬GrA|¬G|4α=↓|4|ε|≤e, |πcheck sign of rA|4α⊗↓|4rX.>
3417 |L|L|¬j|¬a|¬p|L|¬9|¬f|LJump if |→|¬Z. (rA|4|=|↔6α=↓|40)>
3421 |L|L|¬j|¬m|¬p|L|¬8|¬f>|L|¬7|¬h|L|¬e|¬n|¬t|¬x|L|¬1>
3423 |L|L|¬s|¬r|¬c|L|¬1|LMake rA nonzero with same
3428 sign.>|L|L|¬j|¬m|¬p|L|¬8|¬f>|L|¬1|¬h|L|¬j|¬a|¬p|L|¬8|¬f|LJum
3430 p if not |→|¬Z. (rA|4|=|↔6α=↓|40)>|L|¬6|¬h|L|¬e|¬n|¬t|¬a|L|¬
3435 0>|L|¬8|¬h|L|¬c|¬m|¬p|¬a|L|≤$|¬0|≤$|LSet comparison
3438 indicator.>|L|¬9|¬h|L|¬j|¬m|¬p|Lα/↓|LExit from
3441 subroutine.>|Hβ*?*?{U0}{H9L11M29}|π58320#Computer
folio 742 galley 4
3443 Programming!(Knuth/Addison-Wesley)!f. 742!Ans!g.
3445 4c|'{A6}|≡1|≡9|≡.|9|4|≡1|≡9|≡.|9|4Let |ε|≤g|βk|4α=↓|4|≤d|βk|
3447 4α=↓|4|≤h|βk|4α=↓|4|≤s|βk|4α=↓|40 |πfor |εk|4|¬Q|4n.
3450 |πIt su∃ces to _nd the coe∃cient of |εx|β1, |πsince
3459 the coe∃cient of |εx|βk |πwill be the same except
3468 with all subscripts increased by |εk|4α_↓|41.
3474 |πLet |ε(f|βk,|4g|βk) |πdenote the coe∃cient
3479 of |εx|β1 |πin |ε(s|βk|4α_↓|4c|βk,|4c|βk) |πrespectively.
3484 Then |εf|β1|4α=↓|4(1|4α+↓|4|≤h|β1)(1|4α_↓|4|≤g|β1|4α_↓|4|≤g|
3485 β1|≤d|β1|4α_↓|4|≤g|β1|≤s|β1|4α_↓|4|≤d|β1|≤s|β1|4α_↓|4|≤g|β1|
3485 4|≤d|β1|≤s|β1), g|β1|4α=↓|4(1|4α+↓|4|≤d|β1)(1|4α+↓|4|≤h|β1)(
3486 |≤g|β1|4α+↓|4|≤s|β1|4α+↓|4|≤g|β1|≤s|β1), |πand
3488 |εf|βk|4α=↓|4(1|4α_↓|4|≤g|βk|≤s|βk|4α_↓|4|≤d|βk|≤s|βk|4α_↓|4
3488 |≤g|βk|≤d|βk|≤s|βk)f|βk|βα_↓|β1|4α+↓|4(|≤g|βk
3489 α_↓ |≤h|βk α+↓ |≤g|βk|4|≤d|βk α+↓ |≤g|βk|≤h|βk
3495 α+↓ |≤g|βk|4|≤d|βk|≤h|βk α+↓ |≤g|βk|≤h|βk|≤s|βk
3499 α↓ |≤d|βk|≤h|βk|≤s|βk α+↓ |≤g|βk|4|≤d|βk|≤h|βk|≤s|βk)g|βk|βα
3502 _↓|β1, g|βk α=↓ |≤s|βk(1 α+↓ |≤g|βk)(1 α+↓ |≤d|βk)f|βk|βα_↓|
3509 β1 α_↓ (1 α+↓ |≤d|βk(|≤g|βk α+↓ |≤g|βk|≤h|βk
3516 α+↓ |≤h|βk|≤s|βk α+↓ |≤g|βk|≤h|βk|≤s|βk)g|βk|βα_↓|β1,
3520 |πfor |ε1|4|¬W|4k|4|¬E|4n. |πThus |εf|βn α=↓
3525 1 α+↓ |≤h|β1 α_↓ |≤g|β1 α+↓ (4n |πterms of 2nd
3535 order) α+↓ (higher order terms)|4α=↓|41|4α+↓|4|ε|≤h|β1|4α_↓|
3539 4|≤g|β1|4α+↓|4O(n|≤e|g2) |πis su∃ciently small.
3543 [The Kahan summation formula was _rst published
3550 in |εCACM |≡8 (1965), 40; |πcf. |εProc. IFIP
3558 Congress (1971), |≡2|≡, 1232. |πFor another approach
3565 to accurate summation, see R. J. Hanson, |εCACM
3573 |≡1|≡8 (1975), 57<58.]|'{A3}|π|≡2|≡0|≡.|9|4By
3577 the proof of Theorem C, (47) fails for |εe|βw|4α=↓|4p
3586 |πonly if |ε|¬Gv|¬G|4α+↓|4|f1|d32|)|4|¬E|4|¬Fw|4α_↓|4u|¬G|4|
3588 ¬R|4b|gp|gα_↓|g1|4α+↓|4b|gα_↓|g1; |πhence |ε|¬Gf|βu|¬G|4|¬R|
3590 4|¬Gf|βv|¬G|4|¬R|41|4α_↓|4(|f1|d32|)b|4α_↓|41)b|gα_↓|gp.
3591 |πThis rather rare case, in which |ε|¬Gf|βw|¬G
3598 |πbefore normalization takes its maximum value
3604 2, is necessary and su∃cient.|'{A3}|π|≡2|≡1|≡.|9|4(Solution
3610 by G. W. Veltkamp.) Let |εc|4α=↓|42|g|"p|gp|g/|g2|g|"P|4αt↓|
3615 41; |πwe may assume that |εp|4|¬E|42, |πso |εc
3623 |πis redpresentable. First compute |εu|¬S|4α=↓|4u|4|↔N|4c,
3628 u|β1|4α=↓|4(u|4|↔B|4u|¬S)|4|↔V|4u|¬S, u|β2|4α=↓|4u|4|↔B|4u|β
3629 1; v|¬S|4α=↓|4v|4|↔N|4c, v|β1|4α=↓|4(v|4|↔B|4v|¬S)|4|↔V|4v|¬
3631 S, v|β2|4α=↓|4v|4|↔B|4v|β1. |πThen set |εw|4|¬L|4u|4|↔N|4v,
3636 w|¬S|4|¬L|4{H11}({H9}((u|β1|4|↔N|4v|β1|4B|4w)|4|↔V|4(u|β1|4|
3636 ↔N|4v|β2))|4|↔V|4(u|β2|4|↔N|4v|β1){H11}){H9}|4|↔V|4(u|β2|4|↔
3636 N|4v|β2).|'|π!!|2It su∃ces to prove this when
3643 |εu, v|4|¬Q|40 |πand |εe|βu|4α=↓|4e|βu|4α=↓|4p,
3647 |πao that |εu |πand |εv |πare integers|4|¬A|4[|ε2|gp|gα_↓|g1
3653 ,|42|gp). |πThen |εu|4α=↓|4u|β1|4α+↓|4u|β2 |πwhere
3657 |ε2|gp|gα_↓|g1|4|¬E|4u|β1|4|¬E|42|gp, u|β1|4|πmod|4|ε2|g|"p|
3658 gp|g/|g2|"P|4α=↓|40, |πand |ε|¬Gu|β2|¬G|4|¬E|42|g|"p|gp|g/|g
3660 2|g|"P|gα_↓|g1; |πsimilarly |εv|4α=↓|4v|β1|4α↓|4v|β2.
3663 |πThe operations during the calculation of |εw|¬S
3670 |πare exact, because |εw|4α_↓|4u|β1v|β1 |πis
3675 a multiple of 2|ε|gp|gα_↓|g1 |πwith |ε|¬Gw|4α_↓|4u|β1v|β1|¬G
3680 |4|¬E|4|¬Gw|4α_↓|4uv|¬G|4α+↓|4|¬Gu|β2v|β1|4α+↓|4u|β1v|β2|4αt
3680 ↓|4u|β2v|β2|¬G|4|¬E|42|gp|gα_↓|g1|4α↓|42|gp|gα+↓|g|"p|gp|g/|
3680 g2|g|"P|4αt↓|42|gp|gα_↓|g1; |πand |ε|¬Gw|4α_↓|4u|β1v|β1|4α_↓
3682 |4u|β1v|β2|¬G|4|¬E|4|¬Gw|4α_↓|4uv|¬G|4α↓|4|¬Gu|β2v|¬G|4|¬W|4
3682 2|gp|gα_↓|g1|4α+↓|42|g|"p|gp|g/|g2|g|"P|gα_↓|g1|gα+↓|gp,
3683 |πwhere |εw|4α_↓|4u|β1v|β1|4α_↓|4u|β1v|β2 |πis
3686 a multiple of |ε2|g|"p|gp|g/|g2|g|"P.|'|π|≡2|≡2|≡.|9|4We
3691 may assume that |εb|gp|gα_↓|g1|4|¬E|4u, v|4|¬W|4b|gp.
3696 |πIf |εuv|4|¬E|4b|g2|gp|gα_↓|g1 |πthen |εx|β1|4α=↓|4uv|4α_↓|
3699 4r |πwhere |ε|¬Gr|¬G|4|¬E|4|f1|d32|)b|gp|gα_↓|g1,
3702 |πhence |εx|β2|4α=↓|4|πround|ε(u|4α_↓|4r/v)|4α=↓|4x|β0
3704 |π(since |ε|¬Gr/v|¬G|4|¬E|4|f1|d32|)b|gp|gα_↓|g1/b|gp|gα_↓|g
3705 1|4|¬E|4|f1|d32|), |πand equality implies |εv|4α=↓|4b|gp|gα_
3709 ↓|g1 |πhence |εr|4α=↓|40). |πIf |εuv|4|¬Q|4b|g2|gp|gα_↓|g1
3714 |πthen |εx|β1|4α=↓|4uv|4α_↓|4r |πwhere |ε|¬gr|¬g|4|¬E|4|f1|d
3717 32|)b|gp, |πhence |εx|β1/v|4|¬E|4u|4α_↓|4r/v|4|¬W|4b|gp|4α+↓
3719 |4|f1|d32|)b |πand |εx|β2|4|¬E|4b|gp. |πIf |εx|β2|4α=↓|4b|gp
3723 |πthen |εx|β3|4α=↓|4x|β1 |π(for otherwise |εb|gp|4α_↓|4|f1|
3728 d32|))v|4|¬E|4x|β1|4|¬E|4b|gp(v|4α_↓|41)). |πIf
3730 |εx|β2|4|¬W|4b|gp |πand |εx|β1|4|¬Q|4b|g2|gp|gα_↓|g1
3733 |πthen let |εx|β2|4α=↓|4x|β1/v|4α+↓|4q |πwhere
3737 |ε|¬Gq|¬G|4|¬E|4|f1|d32|); |πwe have |εx|β3|4α=↓|4|πround|ε(
3740 x|β1|4αt↓|4qv)|4α=↓|4x|β1. |πFinally if |εx|β2|4|¬W|4b|gp
3744 |πand |εx|β1|4α=↓|4b|g2|gp|gα_↓|g1 |πand |εx|β3|4|¬W|4b|g2|g
3747 p|gα_↓|g1 |πthen |εx|β4|4α=↓|4x|β2 |πby the _rst
3753 case above. This situation arises e.g. for |εb|4α=↓|410,
3761 p|4α=↓|42, u|4α=↓|419, v|4α=↓|455, x|β1|4α=↓|41000,
3765 x|β2|4α=↓|418, x|β3|4α=↓|4990.|'{A9}|π|≡2|≡3|≡.|9|4Let
3768 |ε|"lu|"L|4α=↓|4n, |πso that |εu|4|πmod|41|4α=↓|4|εu|4|↔B|4n
3771 |4α=↓|4u|4α_↓|4n|4α+↓|4r |πwhere |ε|¬Gr|¬G|4|¬E|4|f1|d32|)b|
3773 gα_↓|gp; |πwe wish to show that round|ε(n|4α_↓|4r)|4α=↓|4n.
3780 |πThe result is clear if |ε|¬Gn|¬G|4|¬Q|41; |πand
3787 |εr|4α=↓|40 |πwhen |εn|4α=↓|40 |πor 1, so the
3794 only subtle case is when |εn|4α=↓|4|→α_↓1, r|4α=↓|4|f1|d32|)
3800 b|gα_↓|gp. |πThe identity fails i= |εb |πis a
3808 multiple of 4 and |ε|→α_↓b|gα_↓|g1|4|¬W|4u|4|¬W|4|→α_↓b|gα_↓
3812 |g2 |πand |εu|4|πmod|4|ε2b|gα_↓|gp|4α=↓|4|f3|d32|)b|gα_↓|gp
3815 |π(e.g., |εp|4α=↓|43, b|4α=↓|48, u|4α=↓|4|→α_↓.0124).|'
3819 {A3}|π|≡2|≡4|≡.|9|4Let |εu|4α=↓|4[a,|4b], v|4α=↓|4[c,|4d].
3822 |πThen |εu|4|↔V|4v|4α=↓|4[a|4{H11}|*2+{H9}|4c,|4b|4{H11}|*2∃{H
3823 9}|4d] |πwhere {H11}|*2∃{H9} is commutative, |εx|4{H11}|*2∃{H9
3828 }|410|4α=↓|4x |πfor all |εx, x|4{H11}|*2∃{H9}|4α_↓|40|4α=↓|4x
3832 |πfor all |εx|4|=|↔6α=↓|4|→α+↓0, x|4{H11}|*2∃{H9}|4|→α+↓|→|¬
3836 X|4α=↓|4|→α+↓|→|¬X |πfor all |εx, |πand |εx|4{H11}|*2∃{H9}|4|
3841 →α_↓|→|¬X |πneed'nt be de_ned; |εx|4{H11}|*2+{H9}|4y|4α=↓|4|→
3845 α_↓{H11}({H9}(|→α_↓x)|4{H11}|*2∃{H9} (|→α_↓y){H11}){H9}.
3847 |πAlso |εu|4|↔B|4v|4α=↓|4u|4|↔V|4(|→α_↓v) |πwhere
3850 |ε|→α_↓v|4α=↓|4[|→α_↓d,|4|→α_↓c].|'|π!!|2Let
3852 |εu|4|↔N|4v|4α=↓|4[|πmin(|εa|4{H11}|*2+{H9}|4c,
3853 a|4{H11}|*2+{H9}|4d, b|4{H11}|*2+{H9}|4c, b|4{H11}|*2+{H9}|4d),
3855 |πmax(|εa|4{H11}|*2∃{H9}|4c, a|4{H11}|4|*2∃{H9}|4d,
3858 b|4{H11}|*2∃{H9}|4c, b|4{H11}|*2∃{H9}|4d)], |πwhere
3861 |εx|4{H11}|*2∃{H9}|4y|4α=↓|4y|4{H11}|*2∃{H9}x,
3862 x|4{H11}|*2∃{H9}|4(|→α_↓y)|4α=↓|4|→α_↓(x|4{H11}|*2+{H9}|4y)|4α
3862 =↓|4(|→α_↓x)|4{H11}|*2∃{H9}|4y; x|4{H11}|*2∃{H9}|4|→α+↓0|4α=↓|
3863 4|→α+↓0 |πfor |εx|4|¬Q|40, |→α_↓0 |πfor |εx|4|¬W|40;
3869 x|4{H11}|*2∃{H9}|4|→α_↓0|4α=↓|4|→α_↓(x|4{H11}|*2∃{H9}|4|→α+↓0)
3869 ; x|4{H11}|*2∃{H9}|4|→α+↓|¬X|4α=↓|4|→α+↓|¬X |πfor
3872 |εx|4|¬Q|4|→α+↓0, |→α_↓|¬X|4|πfor |εx|4|¬W|4↓α_↓0.
3875 |π(It is possible to determine the min and max
3884 simply by looking at the signs of |π|εa, b, c,
3894 d, |πthereby computing only two of the eight
3902 products, except when |εa|4|¬W|40|4|¬W|4b |πand
3907 |εc|4|¬W|40|4|¬W|4d; |πin the latter case we
3913 compute four products and the answer is [min|ε(a|4{H11}|*2+{H
3920 9}|4d, b|4{H11}|*2+{H9}|4c), |πmax|ε(a|4{H11}|*2∃{H9}|4c,
3923 b|4{H11}|*2∃{H9}|4d)].)|'!!|2Finally, |εu|4|↔n|4v
3926 |πis unde_ned if |εc|4|¬W|40|4|¬W|4d; |πotherwise
3931 we use the formulas for multiplication with |εc,
3939 d |πreplaced by |εd|gα_↓|g1, c|gα_↓|g1, |πwhere
3945 |εx|4{H11}|*2∃{H9}|4y|gα_↓|g1|4α=↓|4x|4{H11}|*2∃{H9}|4y,
3946 x|4{H11}|*2+{H9}|4y|gα_↓|g1|4α=↓|4x|4{H11}|*2+{H9}|4y,
3947 (|→|¬N0)|gα_↓|g1|4α=↓|4|→|¬N|¬X, (|→|¬N|¬X)|gα_↓|g1|4α=↓|4|→
3948 |¬N0.|'{A3}|π|≡2|≡5|≡.|9|4Cancellation reveals
3951 |εprevious |πerrors in the computation of |εu
3958 |πand |εv. |πFor example, if |ε|≤es|πis small,
3965 we often get poor accuracy when computing |εf(x|4α+↓|4|≤e)|4
3972 |↔B|4f(x), |πbecause the rounded calculation
3977 of |εf(x|4α+↓|4|≤e) |πdestroys much of the information
3984 about |ε|≤e. |πIt is often desirable to reunite
3992 such formulas as |ε|≤e|4|↔N|4g(x,|4|≤e), |πwhere
3997 |εg(x,|4|≤e)|4α=↓|4{H11}({H9}f(x|4α+↓|4|≤e)|4α_↓|4f(x){H11})
3997 /|≤e |πis _rst computed symbolically. Thus, if
4004 |εf(x)|4α=↓|4x|g2 |πthen |εg(x,|4|≤e)|4α=↓|42x|4α+↓|4|≤e;
4007 |πif |εf(x)|4α=↓|4{H11}|¬H{H9}|v4x|) |πthen |εg(x,|4|≤e)|4α=
4010 ↓|41/({H11}|¬H{H9}|v4x|4α+↓|4|≤e|)|4α+↓|4{H11}|¬H{H9}|v4x|))
4010 .|'{A3}{A22}{H10L12}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨2|∨.|∨3
4011 |'{A11}{H9L11}|9|1|≡1|≡.|9|4First, |ε(w|βm,|4w|βi)|4α=↓|4(.5
4013 73,|4.248); |πthen |εw|βmv|βl/v|βm|4α=↓|4.290;
4016 |πso the answer is (.572,|4.958). This in fact
4024 is the correct result to six decimals.|'{A3}|9|1|≡2|≡.|9|4Th
4031 e answer is not a=ected, since the normalization
4039 routine truncates to eight places and can never
4047 look at this particular byte position. (Scaling
4054 to the left occurs at most once during normalization,
4063 since the inputs are normalized.)|'{A3}|9|1|≡3|≡.|9|4Over⊗ow
4068 obviously cannot occur at line 09, since we
4077 are adding two-byte quantities, or at line 22,
4085 since we are adding four-byte quantities. In
4092 line 30 we are computing the sum of three four-byte
4102 quantities, so this cannot over⊗ow. Finally,
4108 in line 32, over⊗ow is impossible because the
4116 product |εf|βuf|βv |πmust be less than unity.|'
4123 {A3}|9|1|≡4|≡.|9|4Insert ``|¬j|¬o|¬v |¬o|¬f|¬l|¬o|≤⊃
4126 |¬e|¬n|¬t|¬1 |¬0'' between lines 03 and 04. Replace
4134 lines 21<22 by ``|¬a|¬d|¬d |¬t|¬e|¬m|¬p|≤#|¬a|¬b|¬s|≤&|≤⊃
4139 |¬j|¬n|¬o|¬v α/↓|≤%|¬2|≤⊃ |¬i|¬n|¬c|¬1 |¬1'',
4143 and change lines 28<31 to ``|¬s|¬l|¬a|¬x |¬5|≤⊃
4150 |¬a|¬d|¬d |¬t|¬e|¬m|¬p|≤⊃ |¬j|¬n|¬o|¬v α/↓|≤%|¬2|≤⊃
4154 |¬i|¬n|¬c|¬1 |¬1|≤⊃ |¬e|¬n|¬t|¬x |¬0|¬, |¬2|≤⊃
4159 |¬s|¬r|¬c |¬5''. This odds _ve lines of code
4167 and only 1, 2, or 3 units of execution time.|'
4177 {A3}|9|1|≡5|≡.|9|4Insert ``|¬j|¬o|¬v |¬o|¬f|¬l|¬o''
4180 after line 06. Change lines 22, 31, 39 respectively
4189 to |¬s|¬r|¬a|¬x |¬0, |¬1|≤⊃ |¬s|¬l|¬a|¬x |¬5|≤⊃
4195 |¬a|¬d|¬d |¬a|¬c|¬c. Between lines 40 and 41,
4202 insert ``|¬d|¬e|¬c|¬2 |¬1|≤⊃ |¬j|¬n|¬o|¬v |¬d|¬n|¬o|¬r|¬m|≤⊃
4206 |¬i|¬n|¬c|¬2 |¬1|≤⊃ |¬i|¬n|¬c|¬x |¬1|≤⊃ |¬s|¬r|¬c
4212 |≤⊃''. [It's tempting to remove the |¬d|¬e|¬c
4219 |¬1 in factor of |¬s|¬t|¬z |¬e|¬x|¬p|¬o, but
4226 then |¬i|¬n|¬c|¬2 |¬1 might over⊗ow vI2*3] This
4233 adds six lines of code; the time |εdecreases
4241 b|πby |ε3u |πunless there is fraction over⊗ow,
4248 when it increases by |ε7u.|'{A3}|9|1|≡6|≡.|E|'
4254 |h|≡6|≡.|9|4|∂|¬d|¬o|¬u|¬b|¬l|¬e!|∂|¬s|¬l|¬a|¬x!|∂|¬t|¬e|¬m|
4254 ¬p|≤#|¬e|¬x|¬p|¬d|≤&!!|∂Correct for di=erence
4257 in excess.|'|h|n|'|∂|¬d|¬o|¬u|¬b|¬l|¬e|L|¬s|¬t|¬j|L|¬e|¬x|¬i
4260 |¬t|¬d|¬f|LConvert to double precision:>|L|L|¬e|¬n|¬t|¬x|¬0|
4264 LClear rX.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬2|L|¬t|¬e
4267 |¬m|¬p|≤#|¬e|¬x|¬p|≤&|LrI2|4|¬L|4|εe.>|L|L|π|¬i|¬n|¬c|¬2|L|¬
4268 q|¬q|≤*/|¬q|LCorrect for di=erence in excess.>
4273 |L|L|¬s|¬t|¬z|L|¬e|¬x|¬p|¬o|L|¬e|¬x|¬p|¬o|4|¬L|40.>
4274 |L|L|¬s|¬l|¬a|¬x|L|¬1|LRemove exponent.>|L|L|¬j|¬m|¬p|L|¬d|¬
4276 n|¬o|¬r|¬m|LNormalize and exit.>|L|¬s|¬i|¬n|¬g|¬l|¬e|L|¬s|¬t
4279 |¬j|L|¬e|¬x|¬i|¬t|¬f|LConvert to single precision:>
4283 |L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|LEnsure over⊗ow is
4286 o=.>|L|L|¬s|¬t|¬a|L|¬t|¬e|¬m|¬p>|L|L|¬l|¬d|¬2|L|¬t|¬e|¬m|¬p|
4288 ≤#|¬e|¬x|¬p|¬d|≤&|LrI2|4|¬L|4|εe.>|π|L|L|¬d|¬e|¬c|¬2|¬q|¬q|≤
4289 */|¬q|LCorrect for di=erence in excess.>|L|L|¬s|¬l|¬a|¬x|L|¬2
4294 |LRemove exponent.>|L|L|¬j|¬m|¬p|L|¬n|¬o|¬r|¬m|LNormalize,
4297 round, and exit.>{A3}|9|1|≡7|≡.|9|4All three
4302 routines give zero as the answer if and only
4311 if the exact result would be zero, so we need
4321 not worry about zero denominators in the expressions
4329 for relative error. The worst case of the addition
4338 rotuine is pretty bad: Visualized in decimal
4345 notation, if the inputs are 1.0000000 and .99999999,
4353 the answer is |εb|gα_↓|g7 |πinstead of |εb|gα_↓|g8:
4360 |πthus the maximum relative error |ε|≤d|β1 |πis
4367 |εb|4α_↓|41, |πwhere |εb |πis the byte size.|'
4374 For multiplication and division, we may assume
4381 that the exponents of both operands are |¬q|¬q,
4389 and that both operands are positive. The maximum
4397 error in multiplication is readily bounded by
4404 considering Fig. 4: When |εuv|4|¬R|41/b, |πwe
4410 have 0|4|¬E|4uv|4α_↓|4u|4|↔N|4v|4|¬W|43b|gα_↓|g9|4α+↓|4(b|4α
4411 _↓|41)b|gα_↓|g9, |πso the relative error is bounded
4418 by (|εb|4α↓|42)b|gα_↓|g8. |πWhen 1/|εb|g2|4|¬E|4uv|4|¬W|41/b
4421 , |πwe have 0|4|¬E|4uv|4α_↓|4u|4|↔N|4v|4|¬W|43b|gα_↓|g9,
4425 |πso the relative error in this case is bounded
4434 by 3|εb|gα_↓|g9/uv|4|¬E|43b|gα_↓|g7. |πWe take
4438 |ε|≤d|β2 |πto be the larger of the two estimates,
4447 namely |ε3b|gα_↓|g7.|'|π!!|2Division requires
4451 a more careful analysis of Program D. The quantity
4460 actually computed by the subroutine is |ε|≤a|4α_↓|4|≤d|4α_↓|
4466 4b|≤e{H11}({H9}(|≤a|4α_↓|4|≤d|¬C)(|≤b|4α_↓|4|≤d|¬S)|4α_↓|4|≤
4466 d|1|9{H11}){H9}|4α_↓|4|≤d|βn |πwhere |ε|≤a|4α=↓|4(u|βm|4α↓|4
4468 |≤eu|βl)/bv|βm, |≤b|4α=↓|4v|βl/bv|βm, |πand |ε|≤d,
4472 |≤d|¬S, |≤d|¬C, |≤d|9|1, |≤d|βn |πare nonnegative
4478 truncation errors with |ε|≤d|4|¬W|4b|gα_↓|g1|g0,
4482 |≤d|¬S|4|¬W|4b|gα_↓|g5, |≤d|¬C|4|¬W|4b|gα_↓|g5,
4484 |≤d|9|1|4|¬W|4b|gα_↓|g6, |πand |ε|≤d|βn |π(which
4488 occurs during normalization) is either less than
4495 |εb|gα_↓|g9 |πor |εb|gα_↓|g8 |πdepending on whether
4501 scaling occurs or not. The actual value of the
4510 quotient is |ε|≤a/(1|4α↓|4b|≤e|≤b)|4α=↓|4|≤a|4α_↓|4b|≤e|≤a|≤
4512 b|4α↓|4b|g2|≤a|≤b|g2|≤d|¬C|¬C, |πwhere |ε|≤d|¬C|¬C
4515 |πis the nonnegative error due to truncatioon
4522 of the in_nite series (3); |ε|≤d|¬C|¬C|4|¬W|4|≤e|g2,
4528 |πsince it is an alternating series. The relative
4536 error is therefore the absolute value of |ε(b|≤e|≤d|¬S|4α↓|4
4543 b|≤e|≤d|¬C|≤b/|≤a|4α↓|4b|≤e|≤d|9|1/|≤a)|4α_↓|4(|≤d/|≤a|4α↓|4
4543 b|≤e|≤d|¬S|≤d|¬C/|≤a|4α↓|4b|g2|≤b|g2|≤d|¬C|¬C|4α+↓|4|≤d|βn/|
4543 ≤a), |πtimes |ε(1|4α↓|4b|≤e|≤b). |πThe positive
4548 terms in this expression are bounded by |εb|gα_↓|g9|4α↓|4b|g
4555 α_↓|g8|4α↓|4b|gα_↓|g8, |πand the negative terms
4560 are bounded by |εb|gα_↓|g8|4α↓|4b|gα_↓|g1|g2|4α↓|4b|gα_↓|g8
4564 |πplus the contribution by the normalizing phase,
4571 which can be about |εb|gα_↓|g7 |πin magnitude.
4578 It is therefore clear that the potentially greatest
4586 part of the relative error comes during the normalization
4595 phase, and that |ε|≤d|β3|4α=↓|4(b|4α↓|42)b|gα_↓|g8
4599 |πis a safe upper bound for the relative error.|'
4608 {A3}|9|1|≡8|≡.|9|4Addition: If |εe|βu|4|¬E|4e|βv|4α↓|41,
4611 |πthe entire relative error occurs during the
4618 normalization phase, so it is bounded above by
4626 |εb|gα_↓|g7. |πIf |εe|βu|4|¬R|4e|βv|4α+↓|42,
4629 |πand it the signs are the same, again the entire
4639 error may be ascribed to normalization; if the
4647 signs are opposite, the error due to shifting
4655 digits out of the register is in the opposite
4664 direction from the subsequent error introduced
4670 during normalization. Both of these errors are
4677 bounded by |εb|gα_↓|g7, |πhence |ε|≤d|β1|4α=↓|4b|gα_↓|g7.
4682 |π(This is substantially better then the result
4689 in exercise 7*3)|'!!|2Multiplication: An analysis
4695 as in {U0}{H9L11M29}|π58320#Computer Programming!(Knuth/Addi
folio 748 galley 5
4698 son-Wesley)!Ans!f. 748!g. 5|'{A23}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O
4701 |∨N|9|∨4|∨.|∨2|∨.|∨4|'{A11}{H9L11}|9|1|≡1|≡.|9|4Since
4703 fraction over⊗ow can occur only when the operands
4711 have the same sign, this is the probability that
4720 fraction over⊗ow occurs divided by the probability
4727 that the operands have the same sign, namely,
4735 7%/|→α_↓|f1|d32|)(91%)|4|¬V|415%.|'{A3}|9|1|≡2|≡.|9|4log|β1|
4736 β0|42.3|4α_↓|4log|β1|β0|42.2|4|¬V|41.930516%.|'
4737 {A3}|9|1|≡4|≡.|9|4The pages would be uniformly
4742 gray (same as ``random point on a slide rule'').|'
4751 {A3}|9|1|≡5|≡.|9|4The probability that |ε10f|βU|4|¬E|4r
4755 |πis |ε(r|4α_↓|41)/10|4α↓|4(r|4α_↓|41)/100|4α+↓|4|¬O|4|¬O|4|
4756 ¬O|4α=↓|4(r|4α_↓|41)/9. |πSo in this case the
4762 leading digits are |εuniformly |πdistributed,
4767 e.g., leading digit 1 occurs with probability
4774 |f1|d39|).|'{A3}|9|1|≡6|≡.|9|4The probability
4777 that there are three leading zero bits is log|β1|β6|42|4α=↓|
4785 4|f1|d34|); the probability that there are two
4792 leading zero bits is log|β1|β6|44|4α_↓|4log|β1|β6|42|4α=↓|4|
4796 f1|d34|); and similarly for the other two cases.
4804 The ``average'' number of leading zero bits is
4812 1|f1|d32|), so the ``average'' number of ``signi_cant
4819 bits'' is |εp|4α↓|4|f1|d32|). |πThe worst case,
4825 |εp|4α_↓|41 |πbits, occurs however with rather
4831 high probability. In practice, it is usually
4838 necessary to base error estimates on the worst
4846 case; in the error analysis of Section 4.2.2,
4854 the upper bound on relative rounding error for
4862 ⊗oating-hex is 2|ε|g1|gα_↓|gp. |πIn the binary
4868 case we can have |εp|4α+↓|41 |πsigni_cant bits
4875 at all times (cf. exercise 4.2.1<3), with relative
4883 rounding errors bounded by 2|ε|gα_↓|g1|gα_↓|gp.
4888 |πExtensive computational experience con_rms
4892 that ⊗oating-binary (even with |εp-|πbit precision
4898 instead of |εp|4α+↓|41) |πproduce signi_cantly
4903 more accurate results than |ε(p|4α+↓|42)-|πbit
4908 ⊗oating-hex.|'!!|2Sweeney's tables show that
4913 hexadecimal arithmetic can be done a little faster,
4921 since fewer cycles are needed when scaling to
4929 the right or normalizing to the left. But this
4938 fact is insigni_cant compared to the substantial
4945 advantages of |εb|4α=↓|42 |πover all other radices
4952 (cf. also Theorem 4.2.2C and exercises 4.2.2<15,
4959 21), especially since ⊗oating-binary can be made
4966 as fast as ⊗oating-hex with only a tiny increase
4975 in total processor cost.|'{A3}|π|9|1|≡7|≡.|9|4Suppose
4980 that |ε|¬K|βm|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓|4F(10|g
4981 k|gm){H11}){H9}|4α=↓|4|πlog|45|ε|gk/|πlog|410|ε|gk
4982 |πand |ε|¬K|βm|4{H11}({H9}(F(10|gk|gm|4|¬O|44|gk)|4α_↓|4F(10
4983 |gk|gm){H11}){H9}|4α=↓|4|πlog|4|ε4|gk/|πlog|4|ε10|gk;
4984 |πthen|'{A3}|↔k|uc|)m|)|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α
4985 _↓|4F(10|gk|gm|4|¬O|44|gk){H11}){H9}|4α=↓|4|πlog|β1|β0|4|f5|
4985 d34|)|;{A9}|πfor all |εk. |πBut now let |ε|≤e
4993 |πbe a small positive number, and choose |ε|≤d|4|¬Q|40
5001 |πso that |εF(x)|4|¬W|4|≤e |πfor 0|4|¬W|4|εx|4|¬W|4|≤d,
5006 |πand choose |εM|4|¬Q|40 |πso that |εF(x)|4|¬}Q|*?{A3}|↔k|uc|
5011 )m|)|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓|4F(10|gk|gm|4|¬O
5011 |44|gk){H11}){H9}|4α=↓|4|πlog|β1|β0|4|f5|d34|)|;
5012 {A9}|πfor all |εk. |πBut now let |ε|≤e |πbe a
5021 small positive number, and choose |ε|≤d|4|¬Q|40
5027 |πso that |εF(x)|4|¬W|4|≤e |πfor 0|4|¬W|4|εx|4|¬W|4|≤d,
5032 |πand choose |εM|4|¬Q|40 |πso that |εF(x)|4|¬Q|41|4α_↓|4|≤e
5038 |πfor |εx|4|¬Q|4M. |πWe can take |εk |πso large
5046 that 10|ε|gα_↓|gk|4|¬O|45|gk|4|¬W|4|≤d |πand
5049 |ε4|gk|4|¬Q|4M; |πhence by the monotonicity of
5055 |εF,|'{A3}|↔k|uc|)m|)|4{H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓
5056 |4F(10|gk|gm|4|¬O|44|gk){H11}){H9}|4|∂|¬E|4|↔k|uc|)m|¬E0|)|4
5056 {H11}({H9}F(10|gk|gm|4|¬O|45|gk)|4α_↓|4F(10|gk|g(|gm|gα_↓|g1
5056 |g)|4|¬O|45|gk){H11}){H9}!|9|;|L!α+↓|4|↔k|uc|)m|¬R0|)|4{H11}
5057 ({H9}F(10|gk|g(|gm|gα+↓|g1|g)|4|¬O|44|gk)|4α_↓|4F(10|gk|gm|4
5057 |¬O|44|gk){H11}){H9}>|Lα=↓|4F(10|gα_↓|gk5|gk)|4αt↓|41|4α_↓|4
5058 F(10|gk4|gk)|4|¬W|42|≤e.>{A3}|9|1|π|≡8|≡.|9|4When
5060 |εs|4|¬Q|4r, P|β0(10|gns) |πis 1 for small |εn,
5067 |πand 0 when |"l10|ε|gns|"L|4|¬Q|4|"l10|gnr|"L.
5071 |πThe least |εn |πfor which this happens may
5079 be arbitrarily large, so no uniform bound can
5087 be given for |εN|β0(|≤e) |πindependent of |εs.
5094 |π(In general, calculus textbooks prove that
5100 such a uniform bound would imply that the limit
5109 function |εS|β0(s) |πwould be continuous, and
5115 it isn't.)|'{A3}|9|1|≡9|≡.|9|4Let |εq|β1, q|β2,|4.|4.|4.
5120 |πbe such that |εP|β0(n)|4α=↓|4q|β1(|fnα_↓1|d50|))|4α+↓|4q|β
5123 2(|fnα_↓1|d51|))|4α+↓|4.|4.|4. |πfor all |εn.
5127 |πIt follows that |εP|βm(n)|4α=↓|41|gα_↓|gmq|β1(|fnα_↓1|d50|
5130 ))|4α+↓|42|gα_↓|gmq|β2(|fnα_↓1|d51|))|4α+↓|4.|4.|4.
5131 |πfor all |εn.|'{A3}|π|≡1|≡0|≡.|9|4When |ε1|4|¬W|4r|4|¬W|410
5135 |πthe generating function |εC(z) |πhas simple
5142 poles at the points |ε1|4α+↓|4w|βr, w|βn|4α=↓|42|≤pn|βi/|πln
5147 |410, |πhence|'{A3}{A6}|εC(z)|4α=↓|4|(|πlog|β1|β0|4|εr|4α_↓|
5149 41|d21|4α_↓|4z|)|4α+↓|4|↔k|uc|)nn0|)|4|(1|4α+↓|4w|βn|d2w|βn|
5149 )|4|(e|gα_↓|gw|rn|π|gl|gn|ε|gr|4α_↓|41|d2|π(ln|410)(|εz|4α_↓
5149 |41|4α_↓|4w|βn)|)|4α+↓|4E(z)|;{A8}|πwhere |εE(z)
5152 |πis analytic in the entire plane. Thus if |ε|≤u|4α=↓|4|πarc
5160 tan(2|ε|≤p/|πln|410),|'{A9}|εc|βm|4|∂α=↓|4|πlog|β1|β0|4|εr|4
5161 α_↓|41|4α_↓|4|(2|d2|πln|410|)|4|↔k|uc|)|εn|¬Q0|)|4|9|6|↔a|(e
5161 |urα_↓w|βn|π|1ln|1|εr|)|)|4α_↓|41|d2|εw|βn(1|4α+↓|4w|βn)|gm|
5161 )|↔s|4α+↓|4e|βm!!!!|;{A4}|Lα=↓|4|πlog|β1|β0|4|εr|4α_↓|41|4α+
5162 ↓|4|(|πsin(|εm|≤u|4α+↓|42|≤p|4|πlog|β1|β0|4|εr)|4α_↓|4|πsin(
5162 |εm|≤u)|d2|≤p(1|4α+↓|44|≤p|g2/|π(ln|410)|g2{H11}){H9}|ε|gm|g
5162 /|g2|)|4α+↓|4O|↔a|(1|d2{H11}({H9}1|4α+↓|416|≤p|g2/|π(ln)|410
5162 (|g2{H11}){H9}|ε|gm|g/|g2|)|↔s.>{A3}|≡1|≡1|≡.|9|4When
5164 (log|ε|βb|4U) |πmod 1 is uniformly distributed
5170 in [0,|41), so is (log|ε|βb|41/U)|4|πmod|41|4α=↓|41|4α_↓|4(|
5174 πlog|ε|βb|4U)|πmod|41. (The latter formula holds
5179 except when |εU |πis a power of |εb, |πbut that
5189 occurs with probability zero.)|'{A3}|≡1|≡2|≡.|9|4|εh(z)|4α=↓
5193 |4|¬J|urz|)1/b|)|4f(x)|4dxg(z/bx)/bx|4α+↓|4|¬J|ur1|)z|)|4f(x
5193 )|4dxg(z/x)/x, |πand |εl(z)|4α=↓|4|¬J|urz|)1/b|)|4f(x)|4dxl(
5195 z/bx)/bx|4α+↓|4|¬J|ur1|)z|)|4f(x)|4dxl(z/x)/x,
5196 |πhence |ε{H11}({H9}h(z)|4α_↓|4l(z){H11}){H9}/l(z)|4α=↓|4|¬J
5197 |urz|)1/b|)|4f(x)|4dx{H11}({H9}g(z/bx)|4α_↓|4l(z/bx){H11}){H
5197 9}/l(z/bx)|4α+↓|4|¬J|ur1|)z|)|4f(x)|4dx{H11}({H9}g(z/x)|4α_↓
5197 |4l(z/x){H11}){H9}/l(z/x). |πSince |εf(x)|4|¬R|40,
5200 |¬G{H11}({H9}h)z)|4α_↓|4l(z){H11})/l(z)|¬G|4|¬E|4|¬J|urz|)1/
5200 b|)|4f(x)|4dxA(g)|4α+↓|4|¬J|ur1|)z|)|4f(x)|4dxA(g)
5201 |πfor all |εz, |πhence |εA(h)|4|¬E|4A(g). |πBy
5207 symmetry, |εA(h)|4|¬E|4A(f). |π[|εBell System
5211 Tech. J. |≡4|≡9 (1970), 1609<1625.]|'{A3}|π|≡1|≡3|≡.|9|4Let
5217 |εX|4α=↓|4|π(log|ε|βb|4U)|πmod|41, |εY|4α=↓|4|π(log|ε|βb|4V)
5218 |πmod 1, so that |εS |πand |εY |πare independently
5227 and uniformly distributed in [0,|41). No left
5234 shift is needed if and only if |εX|4α+↓|4Y|4|¬R|41,
5242 |πand this occurs with probability |f1|d32|).|'
5248 !!|2(Similarly, this needs only the weaker assumption
5255 that both operands independently have the |εsame
5262 |πdistribution.)|'{A3}|≡1|≡4|≡.|9|4For convenience,
5265 the calculations are shown here for |εb|4α=↓|410.
5272 |πIf |εk|4α=↓|40, |πthe probability of a carry
5279 is|'{A9}|↔a|ε|(1|d2|πln|410|)|↔s|g2|↔j|uc|)|ε1|¬Ex,y|¬E10|dx
5280 α+↓y|¬R10|)|4|(dx|d2x|)|4|(dy|d2y|)|1|1.|;{A9}|π(See
5282 Fig. A-7.) The value of the integral is|'{A9}|ε|↔j|ur10|)0|)
5290 |4|(dy|d2y|)|4|↔j|ur10|)10α_↓y|)|4|(dx|d2x|)|4α_↓|42|↔j|ur1|
5290 )0|)|4|(dy|d2y|)|↔j|ur10|)10α_↓y|)|(dx|d2x|)|1|1,|;
5291 |πand|'{A9}|ε|↔j|urt|)0|)|(dy|d2y|)|4|πln|↔a|(1|d21|4α_↓|4|ε
5292 y/10|)|↔s|4α=↓|4|↔j|urt|)0|)|↔a|(1|d210|)|4α+↓|4|(y|d2200|)|
5292 4α+↓|4|(y|g2|d23000|)|4α+↓|4|¬O|4|¬0|4|¬0|↔s|4dy|4α=↓|4|(t|d
5292 210|)|4α+↓|4|(t|g2|d2400|)|4α+↓|4|(t|g3|d29000|)|4α+↓|4|¬O|4
5292 |¬O|4|¬O|4.|;|π(The latter integral is essentially
5298 a ``dilogarithm'' integral.) Hence the probability
5304 of a carry when |εk|4α=↓|40 |πis (1/ln|410)|g2(|ε|≤p|g2/6|4α
5310 _↓|42|4|¬K|βn|β|¬R|β1|41/n|g210|gn)|4α=↓|4.27154.
5311 [Note|*/:|\ |πWhenn |*?*?*?εb|4α=↓|42 |πand |εk|4α=↓|40,
5316 |πfraction over⊗ow |εalways |πoccurs, so this
5322 derivation proves that |ε|¬K|βn|β|¬R|β1|41/n|g22|gn|4α=↓|4|≤
5325 p|g2/12|4α_↓|4|f1|d32|)(|πln|42)|g2.]|'!!|2When
5327 |εk|4|¬Q|40, |πthe probability is|'{A8}|↔a|(1|d2ln|410|)|↔s|
5331 g2|↔j|ur|ε10|g1|gα_↓|gk|)10|gα_↓|gk|)|1|1|(dy|d2y|)|↔j|ur10|
5331 )10α_↓y|)|(dx|d2x|)|4α=↓|4|↔a|(1|d2|πln|410|)|↔s|g2|↔a|↔k|uc
5331 |)n|¬R1|)|4|(1|d2|εn|g210|gn|gk|)|4α_↓|4|↔k|uc|)n|¬R1|)|4|(1
5331 |d2n|g210|gn|g(|gk|gα+↓|g1|g)|)|↔s.|;{A9}|πThus
5333 when |εb|4α=↓|410, |πfraction over⊗ow should
5338 occur with probability .272|εp|β0|4α+↓|4.017p|β1|4α+↓|4.002p
5341 |β2|4α+↓|4|¬O|4|¬O|4|¬O|4. |πWhen |εb|4α=↓|42
5344 |πthe corresponding _gures are |εp|β0|4α+↓|4.655p|β1|4α+↓|4.
5348 288p|β2|4α+↓|4↓137p|β3|4α+↓|4.067p|β4|4α+↓|4|¬O|4|¬O|4|¬O|4.
5348 |'!!|2|πNow if we use the probabilities from
5356 Sweeney's _rst table, dividing by .92 to eliminate
5364 zero operands, and assuming that the probabilities
5371 are independent of the operand signs, we predict
5379 a probability of about 14 percent when |εb|4α=↓|410,
5387 |πinstead of the 15 percent in exercise 1. For
5396 |εb|4α=↓|42, |πwe predict about 48 percent, while
5403 the table yeilds 44 percent. These results are
5411 certainly in agreement within the limits of experimental
5419 error.|'{A3}|≡1|≡5|≡.|9|4When |εk|4α=↓|40, |πthe
5423 leading digit is 1 if and only if there is a
5434 carry. (It is possible for fraction over⊗ow and
5442 subsequent rounding to yield a leading digit
5449 of 2, when |εb|4|¬R|44, |πbut we are ignoring
5457 rounding in this exercise.) The probability of
5464 fraction over⊗ow is .272|4|¬W|4log|β1|β0|42,
5468 as shown in the previous exercise.|'!!|2When
5475 |εk|4|¬Q|40, |πthe leading digit is 1 with probability|'
5483 {A9}|↔a|(1|d2ln|410|)|↔s|g2|↔a|↔j|ur10|ε|g1|gα_↓|gk|)10|gα_↓
5483 |gk|)|1|1|(dy|d2y|)|↔j|ur|)1|¬Ex|¬W2α_↓y!!!|5|)|(dx|d2x|)|↔s
5483 |4|¬W|4|↔a|(1|d2|πln|410|)|↔s|g2|↔a|ε|↔j|ur10|g1|gα_↓|gk|)10
5483 |gα_↓|gk|)|(dy|d2y|)|↔j|ur|)1|¬Ex|¬E2|(dx|d2x|)|↔s|4α=↓|4|πl
5483 og|β1|β0|42.|;{A3}|≡1|≡6|≡.|9|4To prove the hint
5488 [qhich is due to Landu, |εPrace matematyczno-⊂zyczne
5495 |≡2|≡1 (1910), 103<113], |πassume _rst that lim|4sup|4|εa|βn
5501 |4α=↓|4|↔l|4|¬Q|40. |πLet |ε|≤e|4α=↓|4|≤l/(|≤l|4α+↓|44M)
5504 |πand choose |εN |πso that |ε|¬Ga|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+
5509 ↓|4a|βn|¬G|4|¬W|4|f1|d310|)|≤e|≤ln |πfor all
5512 |εn|4|¬Q|4N. |πLet |εn|4|¬Q|4N/(1|4α_↓|4|≤e),
5515 n|4|¬Q|45/|≤e |πbe such that |εa|βn|4|¬Q|4|f1|d32|)|≤l.
5520 |πThen by induction |εa|βn|βα_↓|βk|4|¬R|4a|βn|4α_↓|4kM/(n|4α
5523 _↓|4|≤en)|4|¬Q|4|f1|d34|)|≤l |πfor |ε0|4|¬E|4k|4|¬W|4|≤en,
5526 |πand |ε|¬K|ur|)nα_↓|≤en|¬Wk|¬En|)|4a|βk|4|¬R|4|f1|d34|)|≤l(
5527 |≤en|4α_↓|41)|4|¬Q|4|f1|d35|)|≤l|≤en. |πBut |ε|¬G|¬K|ur|)nα_
5529 ↓|≤en|¬Wk|¬En|4a|βk|¬G|4α=↓|4|¬G|¬K|ur|)1|¬Ek|¬En|)|4a|βk|4α
5529 _↓|4|¬K|ur|)1|¬Ek|¬Enα_↓|≤en|)|4a|βk|¬G|4|¬E|4|f1|d35|)|≤e|≤
5529 ln |πsince |εn|4α_↓|4|≤en|4|¬Q|4N. |πA similar
5534 contradiction applies if lim|4ing|4|εa|βn|4|¬W|40.|'
5538 |π!!|2Assuming that |εP|βm|βα+↓|β1(n)|4|¬M|4|≤l
5541 |πas |εn|4|¬M|4|¬X, |πlet |εa|βk|4α=↓|4P|βm(k)|4α_↓|4|≤l.
5545 |πIf |εm|4|¬Q|40, |πthe |εa|βk |πsatisfy the
5551 hypotheses of the hint (cf. Eq. 4.2.2<15), |εm|4|¬Q|40,
5559 |πthe |εa|βk |πsatisfy the hypotheses of the
5566 hint (cf. Eq. 4.2.2<15), |πsince |ε0|4|¬E|4P|βm(k)|4|¬E|41;
5572 |πhence |εP|βm(n)|4|¬M|4|≤l.|'{A3}|π|≡1|≡7|≡.|9|4See
5575 |εFibonacci Quarterly |≡7 (1969), 474<475. |π(Persi
5581 Diaconis [Ph.D. thesis, Harvard University, 1974]
5587 has shown among other things that the de_nition
5595 of probability by repeated averaging is weaker
5602 than harmonic probability, in the following precise
5609 sense: If lim|ε|βm|β|¬M|β|¬X|4|πlim|4inf|ε|βn|β|¬M|β|¬X|4Pm(
5611 n)|4α=↓|4|πlim|ε|βm|β|¬M|β|¬X|4|πlim|4sup|ε|βn|β|¬M|β|¬X|4P|
5611 βn(n)|4α=↓|4|≤l |πthen the harmonic probability
5616 is |ε|≤l. |πOn the other hand the statement ``10|ε|gk|i2|4|¬
5624 E|4n|4|¬W|410|gk|i2|gα+↓|gk |πfor some integer
5628 |εk|4|¬Q|40'' |πhas logarithmic probability |f1|d32|),
5633 while repeated averaging never settles down to
5640 give it any particular probability.)|'|Hβ{U0}{H9L11M29}|π583
folio 754 galley 6
5645 20#Computer Programming!(Knuth/Addison-Wesley)!f.
5647 754!Ans!g. 6|'{A25}{H10L12}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨3|
5649 ∨.|∨1|'{A11}{H9L11}|9|1|≡2|≡.|9|4If the |εi|πth
5653 number to be added is |εu|βi|4α=↓|4(u|βi|β1u|βi|β2|4.|4.|4.|
5658 4u|βi|βn)|βb, |πuse Algorithm A with step A2
5665 changed to the following:|'{I3.4H}!!|2|≡A|≡2|¬S|≡.|9[Add
5670 digits.] Set |εw|βj|4|¬L|4(u|β1|βj|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|
5672 4u|βm|βj|4α+↓|4k)|πmod|4|εb, |πand |εk|4|¬L|4|"l(u|β1|βj|4α+
5674 ↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|βm|βj|4α+↓|4k)/b|"L.
5675 |π[The maximum value of |εk |πis |εm|4α_↓|41,
5682 |πso step A3 would have to be altered if |εm|4|¬Q|4b.)|'
5692 {A3}{IC}|π|h|∂|9|1|≡3|≡.|9|4|∂|¬2|¬h!|∂|¬e|¬n|¬t|¬2!|∂|¬mα/↓
5692 |¬n|≤*/|¬n|¬,|¬1!!|∂|εMN!!|∂|π(loc itititi|E|n|'
5694 |L|9|1|≡3|≡.|L|L|¬e|¬n|¬t|¬1|L|¬n|L|91>|L|L|L|¬j|¬o|¬v|L|¬o|
5695 ¬f|¬l|¬o|L|91|LEnsure over⊗ow is o=.>|L|L|L|¬e|¬n|¬t|¬a|L|¬0
5699 |L|91|L|εk|4|¬L|40.>|L|L|π|¬2|¬h|L|¬e|¬n|¬t|¬2|L|¬0|L|4|4|εN
5700 |L|π(rI2|4|"o|4next value of |εk)>|L|L|L|π|¬e|¬n|¬t|¬3|L|¬mα
5704 /↓|¬n|≤*/|¬n|¬,|¬1|L|4|4|εN|L|π{H11}({H9}|¬l|¬o|¬c|ε(u|βi|βj)
5704 |4|"o|4|¬u|4α+↓|4n(i|4α_↓|41)|4α+↓|4j{H11}){H9}>
5705 |L|L|π|¬3|¬h|L|¬a|¬d|¬d|L|¬u|¬,|¬3|L|εMN|L|πrA|4|¬L|4rA|4α+↓
5705 |4|εu|βi|βj.|π>|L|L|L|¬j|¬n|¬o|¬v|Lα/↓|≤%|¬2|L|εMN|L>
5707 |π|L|L|L|¬i|¬n|¬c|¬2|¬1|L|ε|6K|L|πCarry one.>
5709 |L|L|L|¬d|¬e|¬c|¬3|L|¬n|L|εMN|L|πRepeat for |εb|4|¬R|4i|4|¬R
5711 |40.|π>|L|L|L|¬j|¬3|¬p|L|¬3|¬b|L|εMN|L|π{H11}({H9}rI3|4|"o|4
5712 |εn(i|4α_↓|41)|4α+↓|4j{H11}){H9}|π>|L|L|L|¬s|¬t|¬a|L|¬w|¬,|¬
5713 1|L|4|4|εN|Lw|βj|4|¬L|4|πrA.>|L|L|L|¬e|¬n|¬t|¬a|L|¬0|¬,|¬2|L
5714 |4|4|εN|Lk|4|¬L|4|πrI2.>|L|L|L|¬d|¬e|¬c|¬1|L|¬1|L|4|4|εN|π>
5716 |L|L|L|¬j|¬i|¬p|L|¬2|¬b|L|4|4|εN|L|πRepeat for
5718 |εn|4|¬R|4j|4|¬R|40.>|L|L|L|π|¬s|¬t|¬a|L|¬w|L|91|LStore
5720 _nal carry in |εw|β0.>{A9}|πRunning time, assuming
5727 that |εK|4α=↓|4|f1|d32|)MN, |πis 5.5|εMN|4α+↓|47N|4α+↓|44
5731 |πcycles.|'{A3}|π|9|1|≡4|≡.|9|4We may make the
5736 following assertion before A1: |ε``n|4|¬R|41;
5741 |πand 0|4|¬E|4|εu|βi, v|βi|4|¬W|4b |πfor |ε1|4|¬E|4i|4|¬E|4n
5745 .'' |πBefore A2, we assert: ``1|4|¬E|4|εj|4|¬E|4n;
5751 0|4|¬E|4u|βi, v|βi|4|¬W|4b |πfor 1|4|¬E|4|εi|4|¬E|4n;
5755 0|4|¬E|4w|βi|4|¬W|4b |πfor |εj|4|¬W|4i|4|¬E|4n;
5758 |π0|4|¬E|4|εk|4|¬E|41; |πand|'{A9}|ε(u|βj|βα+↓|β1|4.|4.|4.|4
5760 u|βn)|βb|4α+↓|4(v|βj|βα+↓|β1|4.|4.|4.|4v|βn)|βb|4α=↓|4(kw|βj
5760 |βα+↓|β1|4.|4.|4.|4w|βn)|βb.''|;{A9}|πThe latter
5763 statement means more precisely that|'{A3}|ε|↔k|uc|)j|¬Wt|¬En
5768 |)|4u|βtb|gn|gα_↓|gt|4α+↓|4|↔k|uc|)j|¬Wt|¬En|)|4v|βtb|gn|gα_
5768 ↓|gt|4α=↓|4kb|gn|gα_↓|gj|4α+↓|4|↔k|uc|)j|¬Wt|¬En|)|4w|βtb|gn
5768 |gα_↓|gt.|;{A9}*?*?*?*?|πBefore A3, we assert: ``1|4|¬E|4|εj|4|¬
5773 E|4n; 0|4|¬E|4u|βi, v|βi|4|¬W|4b |πfor 1|4|¬E|4|εi|4|¬E|4n;
5778 0|4|¬E|4w|βi|4|¬W|4b |πfor |εj|4|¬E|4i|4|¬E|4n;
5781 0|4|¬E|4k|4|¬E|41; |πand |ε(u|βj|4.|4.|4.|4u|βn)|βb|4α+↓|4(v
5783 |βj|4.|4.|4.|4v|βn)|βb|4α=↓|4(kw|βj|4.|4.|4.|4w|βn)|βb.''
5784 |πAfter A3, we assert that 0|4|¬E|4|εw|βi|4|¬W|4b
5790 |πfor 1|4|ε|¬E|4i|4|¬E|4n; 0|4|¬E|4w|β0|4|¬E|41;
5793 |πand |ε(u|β1|4.|4.|4.|4u|βn)|βb|4α+↓|4(v|β1|4.|4.|4.|4v|βn)
5794 |βb|4α=↓|4(w|β0|4.|4.|4.|4w|βn)|βb.|'!!|2|πIt
5796 is a simple matter to complete the proof by verifying
5806 the necessary implications between the assertions
5812 and by showing that the algorithm always terminates.|'
5820 {A3}{I3.1H}|9|1|≡5|≡.|9|4|≡B|≡1|≡.|9Set |εj|4|¬L|41,
5822 w|β0|4|¬L|40.|'!!|2|π|≡B|≡2|≡.|9Set |εt|4|¬L|4u|βj|4α+↓|4v|β
5824 j, w|βj|4|¬L|4t|4|πmod|4|εb, i|4|¬L|4j.|'!!|2|π|≡B|≡3|≡.|9If
5827 |εt|4|¬R|4b, |πset |εi|4|¬L|4i|4α_↓|41, t|4|¬L|4w|βi|4α+↓|4
5831 1, w|βi|4|¬L|4t|4|πmod|4|εb, |πand repeat this
5836 step until |εt|4|¬L|4b.|'!!|2|π|≡B|≡.|9Increase
5840 |εj |πby one, and if |εj|4|¬E|4n |πgo back to
5849 B2.|'{A3}|9|1|≡6|≡.|9|4|2|≡C|≡1|≡.|9Set |εj|4|¬L|41,
5852 i|4|¬L|40, r|4|¬L|40.|'!!|4|π|≡C|≡2|≡.|9|4Set
5855 |εt|4|¬L|4u|βj|4α+↓|4v|βj. |πIf |εt|4|¬R|4b,
5858 |πset |εw|βi|4|¬L|4r|4α+↓|41, w|βk|4|¬L|40 |πfor
5862 |εi|4|¬W|4k|4|¬W|4j, |πset |εi|4|¬L|4j, |πand
5866 |εr|4|¬L|4t|4|πmod|4|εb. |πOterwise if |εt|4|¬W|4b|4α_↓|41,
5870 |πset |εw|βi|4|¬L|4r, w|βk|4|¬L|4b|4α_↓|41 |πfor
5874 |εi|4|¬W|4k|4|¬W|4j, |πset |εi|4|¬L|4j, |πand
5878 |εr|4|¬L|4t.|'!!|4|π|≡C|≡3|≡.|9Increase |εj |πby
5882 one. If |εj|4|¬E|4n, |πgo back to C2; otherwise
5890 set |εw|βi|4|¬L|4r, |πand |εw|βk|4|¬L|4b|4α_↓|41
5894 |πfor |εi|4|¬W|4k|4|¬E|4n.|'{A3}{IC}|π|9|1|≡7|≡.|9|4When
5897 |εj|4α=↓|43, |πfor example, we hjave |εk|4α=↓|40
5903 |πwith probability |ε(b|4α+↓|41)/2b, k|4α=↓|41
5907 |πwith probability |ε{H11}({H9}(b|4α_↓|41)/2b{H11}){H9}(1|4α
5909 _↓|41/b), |πnamely the probability that a carry
5916 occurs and thathe preceding digit wasn't |εb|4α_↓|41;
5923 k|4α=↓|42 |πwith probability {H11}({H9}(|εb|4α_↓|41)/2b{H11}
5926 ){H9}(1|4α_↓|41/b); |πand |εk|4α=↓|43 |πwith
5930 probability {H11}({H9}(|εb|4α_↓|41)/2b{H11}){H9}(1/b)(1/b)(1
5931 ). |πFor _xed |εk |πwe may add the probabilities
5940 as |εj |πvaries from 1 to |εn; |πthis gives the
5950 mean number of times the carry propagates back
5958 |εk |πplaces,|'{A9}|εm|βk|4α=↓|4|(b|4α_↓|41|d22b|gk|){H11}|↔
5960 a{H9}(n|4α+↓|41|4α_↓|4k)|↔a1|4α_↓|4|(1|d2b|)|↔s|4α+↓|4|(1|d2
5960 b|){H11}|↔s{H9}.|;{A9}|πAs a check, we _nd that
5967 the average number of carries is|'{A9}|εm|β1|4α+↓|42m|β2|4α+
5973 ↓|4|¬O|4|¬O|4|¬O|4α+↓|4nm|βn|4α=↓|4|(1|d22|){H11}|↔a{H9}n|4α
5973 _↓|4|(1|d2b|4α_↓|41|)|↔a1|4α_↓|4|↔a|(1|d2b|)|↔s|gn|↔s{H11}|↔
5973 s{H9},|;{A9}|πin agreement with (6).|'{A3}|π|h|9|1|∂|≡8|≡.|9
5978 |4|∂|¬1|¬h!|∂|¬e|¬n|¬n|¬i!|∂|¬u|≤%|¬n|≤%|¬1|¬,|¬1!!|∂|εN!!!!
5978 |∂|¬2|¬h!|π|∂|¬i|¬n|¬c|¬a!|∂|¬w|≤%|¬n|≤%|¬1|¬,|¬2!!|∂|εK|E|n
5978 |;|π|L|≡8|≡.|L|¬e|¬n|¬n|¬i|L|¬n|L1|L|¬2|¬h|L|¬l|¬d|¬a|L|¬w|≤
5979 %|¬n|≤%|¬1|¬,|¬2|L|εK>|π|L|L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|L1|L|L
5980 |¬i|¬n|¬c|¬a|L|¬1|L|εK>|L|L|L|¬s|¬t|¬z|π|L|¬w|L1|L|L|¬s|¬t|¬
5981 a|L|¬w|≤%|¬n|≤%|¬1|¬,|¬2|L|εK|π>|L|L|¬1|¬h|L|¬l|¬d|¬a|L|¬u|≤
5982 %|¬n|≤%|¬1|¬,|¬1|L|εN|L|L|π|¬d|¬e|¬c|¬2|L|¬1|L|εK>
5983 |π|L|L|L|¬a|¬d|¬d|L|¬v|≤%|¬n|≤%|¬1|¬,|¬1|L|εN|L|L|π|¬j|¬o|¬v
5983 |L|¬2|¬b|ε|LK|π>|L|L|L|¬s|¬t|¬a|L|¬w|≤%|¬n|≤%|¬1|¬,|¬1|ε|LN|
5984 π|L|¬3|¬h|L|¬i|¬n|¬c|¬2|L|¬1|ε|LN>|π|L|L|L|¬j|¬n|¬o|¬v|L|¬3|
5985 ¬f|ε|LN|π|L|¬3|¬h|L|¬i|¬n|¬c|¬2|L|¬1|ε|LN>|π|L|L|L|¬e|¬n|¬t|
5986 ¬2|L|≤*/|¬1|¬,|¬1|ε|LL>{A9}|πThe running time
5990 depends on |εL, |πthe number of positions in
5998 which |εu|βj|4α↓|4v|βj|4|¬R|4b; |πand on |εK,
6003 |πthe total number of carries. It is not di∃cult
6012 to see that |εK |πis the same quantity analysis
6021 in the text shows that |εL |πhas the average
6030 value |εN{H11}({H9}(b|4α_↓|41)/2b{H11}){H9},
6032 |πand |εK |πhas the average value |f1|d32|)(|εN|4α_↓|4b|gα_↓
6038 |g1|4α_↓|4b|gα_↓|g2|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4b|gα_↓|gn).
6039 |πSo if we ignore terms of order 1/|εb, |πthe
6048 running time is |ε9N|4α↓|4L|4α+↓|47K|4α+↓|43|4|¬V|413N|4α+↓|
6051 43 |πcycles.|'!!|2|εNote|*/:|\ |πSince a carry
6057 occurs almost half of the time, it would be more
6067 e∃cient to delay storing the result by one step.
6076 This leads to a somewhat longer program whose
6084 running time is approximately 12|εN|4α+↓|455
6089 *?*?!!|2|εNote|*/:|\ |πSince a carry occurs almost
6095 half of the time, it would be more e∃cient to
6105 delay storing the result by one step. This leads
6114 to a somewhat longer program whose running time
6122 is approximately 12|εN|4α+↓|45 |πcycles, based
6127 on the somewhat more detailed information calculated
6134 in exercise 7.|'{A3}|9|1|≡9|≡.|9|4Replace |ε``b''
6139 |πby |ε``b|βn|βα_↓|βj'' |πeverywhere in step
6144 A2.|'{A3}|≡1|≡0|≡.|9|4If lines 06 and 07 were
6151 interchanged, we would almost always have over⊗ow,
6158 but register A might have a negative value at
6167 line 08, so this would not work. If the instructions
6177 on lines 05 and 06 were interchanged, the sequence
6186 of over⊗ows occurring in the program would be
6194 slightly di=erent in some cases, but the program
6202 would still be right.|'{A3}|≡1|≡1|≡.|9|4(a) Set
6208 |εj|4|¬L|41; |π(b) if |εu||≡1|≡1|≡.|9|4(a) Set
6213 |εj|4|¬L|41; |π(b) if |εu|βj|4|¬W|4v|βj, |πterminate
6218 |ε[u|4|¬W|4v]; |πif |εu|βj|4α=↓|4v|βj |πand |εj|4α=↓|4n,
6223 |πterminate |ε[u|4α=↓|4v]; |πif |εu|βj|4α=↓|4v|βj
6227 |πand |εj|4|¬W|4n, |πset |εj|4|¬L|4j|4αt↓|41
6231 |πand repeat (b); if |εu|βj|4|¬Q|4v|βj, |πterminate
6237 |ε[u|4|¬Q|4v]. |πThis algorithm tends to be quite
6244 fast, since there is usually low probability
6251 that |εj |πwill have to get very high before
6260 we encounter a case with |εu|βj|4|=|↔6α=↓|4v|βj.|'
6266 {A3}|π|≡1|≡2|≡.|9|4Use Algorithm S with |εu|βj|4α=↓|40
6271 |πand |εv|βj|4α=↓|4w|βj. |πAnother ``borrow''
6275 will occur at the end of the algorithm, which
6284 this time should be ignored.|'{A3}|≡1|≡3|≡.|9|4|∂!|6!|∂|¬e|¬
6289 n|¬t|¬x!|∂|¬n!!|4|4|4!!|∂1|'|L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|L1>
6291 |L|L|¬e|¬n|¬t|¬x|L|¬o|L1>|L|¬2|¬h|L|¬s|¬t|¬x|L|¬c|¬a|¬r|¬r|¬
6292 y|L|εN|π>|L|L|¬l|¬d|¬a|L|¬u|¬,|¬1|ε|LN|π>|L|L|¬m|¬u|¬l|L|¬v|
6294 L|εN|π>|L|L|¬s|¬l|¬c|L|¬5|εN|π>|L|L|¬a|¬d|¬d|L|¬c|¬a|¬r|¬r|¬
6296 y|ε|LN|π>|L|L|¬j|¬n|¬o|¬v|Lα/↓|≤%|¬2|ε|LN|π>|L|L|¬ki*?*?*?*?x|L|
6298 ¬1|ε|LK|π>|L|L|¬s|¬t|¬a|L|¬w|¬,|¬1|ε|LN>|π|L|L|¬d|¬e|¬c|¬1|L
6300 |¬1|ε|LN|π>|L|L|¬j|¬1|¬p|L|¬2|¬b|ε|LN|π>|L|L|¬s|¬t|¬x|L|¬w|L
6302 1>{A9}The running time is 23|εN|4α↓|4K|4α+↓|45
6308 |πcycles, and |εK |πis roughly |ε|f1|d32|)N.|'
6314 {A3}|π|≡1|≡4|≡.|9|4The key inductive assertion
6318 is the one which should be valid at the beginning
6328 of step M4; all others are readily _lled in from
6338 this one, which is as follows: ``1|4|¬E|4|εi|4|¬E|4n;
6345 1|4|¬E|4j|4|¬E|4m; 0|4|¬E|4u|βr|4|¬W|4b |πfor
6348 |ε1|4|¬E|4r|4|¬E|4n; 0|4|¬E|4v|βr|4|¬W|4b |πfor
6351 |ε1|4|¬E|4r|4|¬E|4m; 0|4|¬E|4w|βr|4|¬W|4b |πfor
6354 |εj|4|¬W|4r|4|¬E|4m|4α+↓|4n; 0|4|¬E|4k|4|¬W|4b;
6356 |πand|'{A9}|ε(w|βj|βα↓|β1|4.|4.|4.|4w|βm|βα+↓|βn)|βb|4α+↓|4k
6357 b|gm|gα+↓|gn|gα_↓|gi|gα_↓|gj|4α=↓|4u|4α⊗↓|4(v|βj|βα+↓|β1|4.|
6357 4.|4.|4v|βm)|βb|4α+↓|4(u|βi|βα+↓|β1|4.|4.|4.|4u|βn)|βb|4α⊗↓|
6357 4v|βjb|gm|gα_↓|gj*2.*?*?*?*?{A9}|ε(w|βj|βα↓|β1|4.|4.|4.|4w|βm|βα+
6357 ↓|βn)|βb|4α+↓|4kb|gm|gα+↓|gn|gα_↓|gi|gα_↓|gj|4α=↓|4u|4α⊗↓|4(
6357 v|βj|βα+↓|β1|4.|4.|4.|4v|βm)|βb|4α+↓|4(u|βi|βα+↓|β1|4.|4.|4.
6357 |4u|βn)|βb|4α⊗↓|4v|βjb|gm|gα_↓|gj.''|;{A9}|π(For
6359 the precise meaning of this notation, see the
6367 answer to exercise 4.)|'{A3}|≡1|≡5|≡.|9|4The
6372 error is nonnegative and less than |ε(n|4α_↓|42)b|gα_↓|gn|gα
6378 _↓|g1. |π{H11}({H9}Similarly, if we ignore the
6384 products with |εi|4α+↓|4j|4|¬Q|4n|4α+↓|43, |πthe
6388 error is bounded by |ε(b|4α_↓|43)b|gα_↓|gn|gα_↓|g2,
6393 |πetc.; but, in qome cases, we must compute all
6402 of the products if we want to get the true rounded
6413 result.{H11}){H9}|'{A3}|≡1|≡6|≡.|9|4|≡S|≡1|≡.|9Set
6415 |εr|4|¬L|40, j|4|¬L|41.|'!!|2|π|≡S|≡2|≡.|9Set
6418 |εw|βj|4|¬L|4|"l(rb|4α+↓|4u|βj)/v|"L, r|4|¬L|4(rb|4α+↓|4u|βj
6419 )|πmod|4|εv.|'!!|2|π|≡S|≡3|≡.|9Increase |εj |πby
6423 1, and return to S2 if |εj|4|¬E|4n.|'{A3}|π|≡1|≡7|≡.|9|4|εu/
6430 v|4|¬Q|4u|β0b|gn/(v|β1|4α+↓|41)b|gn|gα_↓|g1|4α=↓|4b({H11}({H
6430 9}1|4α_↓|41/(v|β1|4αt↓|41){H11}){H9}|4|¬Q|4b{H11}({H9}1|4α_↓
6430 |41/(b/2){H11}){H9}|4α=↓|4b|4α_↓|42.|'{A3}|π|≡1|≡8|≡.|9|4|ε(
6431 u|β0b|4α+↓|4u|β1)/(v|β1|4α+↓|41)|4|¬E|4u/(v|β1|4α+↓|41)b|gn|
6431 gα_↓|g1|4|¬W|4u/v.|'{A3}|π|≡1|≡9|≡.|9|4|εu|4α_↓|4|=7qv|4|¬E|
6432 4u|4α_↓|4|=7qv|β1b|gn|gα_↓|g1|4α_↓|4|=7qv|β2b|gn|gα_↓|g2|4α=
6432 ↓|4u|β2b|gn|gα_↓|g2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4u|βn|4α+↓|44*?*?
6432 |gn|gα≠↓*4g1|4α_↓|4|=7qv|β2b|gn|gα_↓|g2|4|¬W|4b|gn|gα_↓|g2(u|
6432 β2|4α+↓|41|4α+↓|4|=7rb|4α_↓|4|=7qv|β2)|4|¬E|40.
6433 |πSince |εu|4α_↓|4|=7qv|4|¬W|40, q|4|¬W|4|=7q.|'
6436 {A3}|π|≡2|≡0|≡.|9|4If |εq|4|¬E|4|=7q|4α_↓|42,
6438 |πthen |εu|4|¬W|4(|=7q|4α_↓|41)v|4|¬W|4|=7q(v|β1b|gn|gα_↓|g1
6439 |4α+↓|4(v|β2|4α+↓|41)b|gn|gα_↓|g2{H11}){H9}|4α_↓|4v|4|¬W|4|=
6439 7qv|β1b|gn|gα_↓|g1|4α+↓|4|=7qv|β2b|gn|gα_↓|g2|4α+↓|4b|gn|gα_
6439 ↓|g1|4α_↓|4v|4|¬E|4|=7qv|β1b|gn|gα_↓|g1|4α+↓|4(b|=7r|4α+↓|4u
6439 |β2)b|gn|gα_↓|g2|4α+↓|4b|gn|gα_↓|g1|4α_↓|4v|4α=↓|4u|β0b|gn|4
6439 α+↓|4u|β1b|gn|gα_↓|g1|4α+↓|4u|β2b|gn|gα_↓|g2|4α+↓|4b|gn|gα_↓
6439 |g1|4α_↓|4v|4|¬E|4u|β0b|gn|4α+↓|4u|β1b|gn|gα_↓|g1|4α+↓|4u|β2
6439 b|gn|gα_↓|g2|4|¬E|4u. |πIn other words, |εu|4|¬W|4u,
6444 |πand this is a contradiction.|'{A3}|≡2|≡1|≡.|9|4Assume
6450 that |εu|4α_↓|4qv|4|¬W|4(1|4α_↓|43/b)v; |πthen
6453 |ε|=7q(v|4α_↓|4b|gn|gα_↓|g2)|4|¬W|4|=7q(v|β1b|gn|gα_↓|g1|4α+
6453 ↓|4v|β2b|gn|gα_↓|g2)|4|¬E|4u|β0b|gn|4α+↓|4u|β1b|gn|gα_↓|g1|4
6453 α+↓|4u|β2b|gn|gα_↓|g2|4|¬E|4u; |πhence |ε1|4α=↓|4|=7q|4α_↓|4
6455 q|4|¬W|4u/(v|4α_↓|4b|gn|gα_↓|g2)|4α_↓|4u/v|4α+↓|41|4α_↓|43/b
6455 ; |πthat is,|'{A3}|ε|(3|d2b|)|4|¬W|4|(u|d2v|)|↔a|(b|gn|gα_↓|
6458 g2|d2v|4α_↓|4b|gn|gα_↓|g2|)|↔s|4|¬W|4|↔a|(b|gn|gα_↓|g1|d2v|4
6458 α_↓|4b|gn|gα_↓|g2|)|↔s.|;{A8}|πFinally, therefore,
6461 |εb|gn|4α+↓|43b|gn|gα_↓|g2|4|¬Q|43v; |πbut this
6464 contradicts the size of |εv|β1, |πunless |εb|4|¬E|43,
6471 |πand the exercise is obviously true when |εb|4|¬E|43.|'
6479 |Hβ{U0}{H9L11M29}|π58320#Computer Programming!(Knuth/Addison
folio 758 galley 7
6480 -Wesley)!f. 758!Ans!g. 7|'{A6}|≡2|≡2|≡.|9|4Let
6484 |εu|4α=↓|44100, v|4α=↓|4588. |πWe _rst try |ε|=7q|4α=↓|4|"l|
6489 f41|d35|)|"L|4α=↓|48, |πbut 8|4|¬O|48|4|¬Q|410(41|4α_↓|440)|
6491 4α+↓|40|4α=↓|410. Then we set |ε|=7q|4α=↓|47,
6496 |πand now we _nd 7|4|¬O|48|4|¬W|410(41|4α_↓|435)|4α+↓|40|4α=
6500 ↓|460. But 7 times 588 equals 4116, so the true
6510 quotient is |εq|4α=↓|46. |π(Incidentally, this
6515 example shows that Theorem B cannot be improved
6523 under the given hypotheses, when |εb|4α=↓|410.)|'
6529 {A3}|π|≡2|≡3|≡.|9|4Obviously |εv|"lb/(v|4α+↓|41)|"L|4|¬W|4(v
6530 |4α+↓|41)|"lb/(v|4α+↓|41)|"L|4|¬E|4(v|4α+↓|41)b/(v|4α+↓|41)|
6530 4α=↓|4b; |πalso if |εv|4|¬R|4|"lb/2|"L |πwe obviously
6536 have |εv|"lb/(v|4α+↓|41)|"L|4|¬R|4v|4|¬R|4|"lb/2|"L.
6538 |πFinally, assume that |ε1|4|¬E|4v|4|¬W|4|"lb/2|"L.
6542 |πThen |εv|"lb/(v|4α+↓|41)|"L|¬Q|4v{H11}(b/(v|4α+↓|41)|4α_↓|
6543 41{H11}){H9}|4|¬R|4b/2|4α_↓|41|4|¬R|4|"lb/2|"L|4α_↓|41,
6544 |πbecause |εv{H11}({H9}b/(v|4α+↓|41)|4α_↓|41{H11}){H9}|4α_↓|
6545 4b/2|4α+↓|41|4α=↓|4(b/2|4α_↓|4v|4α_↓|41)(v|4α_↓|41)/(v|4α+↓|
6545 41)|4|¬R|40. |πFinally since |εv|"lb/(v|4α+↓|41)|"L|4|¬Q|4|"
6548 lb/2|"L|4α_↓|41, |πwe must have |εv|"lb/(v|4α+↓|41)|"L|4|¬R|
6552 4|"lb/2|"L.|'{A3}|π|≡2|≡4|≡.|9|4The probability
6555 is only log|ε|βb|42, not |f1|d32|)*3 |π(For example,
6562 if |εb|4α=↓|42|g3|g5, |πthe probability is approximately
6568 |f1|d335|); this is still high enough too warrant
6576 the special test for |εd|4α=↓|41 |πin steps D1
6584 and D8.)|'{A3}|≡2|≡5|≡.|'{A3}|h|∂!!|2|∂000!|∂|¬2|¬h!|∂|¬e|¬n
6587 |¬t|¬a!|?|¬d|¬i|¬v|¬b|¬y|¬z|¬e|¬r|¬o!|∂!|εA(M|4α+↓|4N)!|∂!|π
6588 Otherwise compute |εb/(v|β1|4α+↓|41).|∂|E|n|'
6591 |>|;|*/|↔c|↔c|↔P|'|;|\|π|¬e|¬n|¬t|¬a|'|¬1|'1|;
6598 >|>|;|*/|↔c|↔c|↔L|\|'|;|¬a|¬d|¬d|'|¬v|≤%|¬1|'1|;
6606 >|>|;|*/|↔c|↔c|↔M|\|'|;|¬s|¬t|¬a|'|¬t|¬e|¬m|¬p|'
6613 1|;>|>|;|*/|↔c|↔c|↔C|'|\|;|¬e|¬n|¬t|¬a|'|¬1|'1|;
6622 >|>|;|*/|↔c|↔c|↔o|'|;|\|¬j|¬o|¬v|'|¬1|¬f|'1|;Jump
6631 if |εv|β1|4α=↓|4b|4α_↓|41.|'>|>|;|*/|↔c|↔c|↔p|\|'
6637 |;|π|¬e|¬n|¬t|¬x|'|¬0|'1|;>|>|;|*/|↔c|↔c|↔l|\|'
6645 |;|¬d|¬i|¬v|'|¬t|¬e|¬¬m|¬|;|¬d|¬i|¬v|'|¬t|¬e|¬m|¬p|'
6650 1|;Otherwise compute |εb/(v|β1|4α+↓|41).|'>|>
6656 |;|π|*/|↔c|↔c|↔m|'|\|;|¬j|¬o|¬v|'|¬d|¬i|¬v|¬b|¬y|¬z|¬e|¬r|¬o|
6660 '1|;Jump if |εv|β1|4α=↓|40.|'>|>|;|*/|↔c|↔O|↔c|\|'
6669 |π|¬1|¬h|'|¬s|¬t|¬a|'|¬d|'1|;>|>|;|*/|↔c|↔O|↔O|\|'
6677 |;|¬d|¬e|¬c|¬a|'|¬1|'1|;>|>|;|*/|↔c|↔O|↔P|\|'|;
6686 |¬j|¬a|¬n|¬z|'α/↓|≤%|¬3|'1|;Jump if |εd|4|=|↔6α=↓|41.|'
6692 >|>|;|*/|↔c|↔O|↔L|'|;|\|¬s|¬t|¬z|'|¬u|'1|4α_↓|4A|;
6700 >|>|;|π|*/|↔c|↔O|↔M|\|'|;|¬j|¬m|¬p|'|¬d|¬2|'|ε1|4α_↓|4A|;
6708 >|>|;|π|*/|↔c|↔O|↔C|\|'|;|¬e|¬n|¬t|¬1|'|¬n|'|εA|;
6716 |πMultiply |εv |πby |εd.|'>|>|;|π|*/|↔c|↔O|↔o|'
6724 |;|\|¬e|¬n|¬t|¬x|'|¬0|'|εA|;>|>|;|π|*/|↔c|↔O|↔p|\|'
6732 |¬2|¬h|'|¬s|¬t|¬x|'|¬c|¬a|¬r|¬r|¬y|'|εAN|;>|>
6738 |;|π|*/|↔c|↔O|↔l|\|'|;|¬l|¬d|¬a|'|¬v|¬,|¬1|'|εAN|;
6744 >|>|;|π|*/|↔c|↔O|↔m|\|'|;|¬m|¬u|¬l|'|¬d|'|εAN|;
6752 >|>|;|2.|5.|5.|'|;|;|;|;|π(as in exercise 13)|'
6764 >|>|;|*/|↔c|↔P|↔o|'|;|\|¬j|¬1|¬p|'|¬2|¬b|'|εAN|;
6772 >|>|;|π|*/|↔c|↔P|↔p|\|'|;|¬e|¬n|¬t|¬1|'|¬m|≤%|¬n|'
6779 |εA|;|π(Now rX|4α=↓|40.)|'>|>|;|*/|↔c|↔P|↔l|\|'
6786 |¬2|¬h|'|¬s|¬t|¬x|'|¬c|¬a|¬r|¬r|¬y|'|εA(M|4α+↓|4N)|;
6790 |πMultiply |εu |πby |εd.|'>|>|;|π|*/|↔c|↔P|↔m|\|'
6798 |;|¬l|¬d|¬a|'|¬u|¬,|¬1|'|εA(M|4α+↓|4N)|;>|>|;
6805 |2.|5.|5.|'|;|;|;|;|π(as in exercise 13)|'>|>
6816 |;|*/|↔c|↔L|↔p|\|'|;|¬j|¬1|¬p|'|¬2|¬b|'|εA(M|4α+↓|4N)|'
6822 >|>|;|π|*/|↔c|↔L|↔l|'|;|\|¬s|¬t|¬x|'|¬u|'|εA|;
6830 >{A3}|π|≡2|≡6|≡.|9|4(See the algorithm of exercise
6836 16.)|'{A3}|h|∂!!|2000!|∂|¬d|¬h!|∂|¬e|¬n|¬n|¬i!|∂|¬u|≤%|¬m|≤%
6837 |¬n|≤%|¬1|¬,|¬,!|∂|εAN!|∂!|π(Remainder|6will|6be|6left|6in|6
6837 loca-|∂|E|n|'|>!!|2|*/|↔O|↔c|↔O|'|\|¬d|¬8|'|¬l|¬d|¬a|'
6842 |¬d|'1!|;!(Remainder will be left in loca-|'>
6851 |>!!|2|*/|↔O|↔c|↔P|'|;|\|¬d|¬e|¬c|¬a|'|¬1|'1!|;
6857 !!tions |¬u|≤%|¬m|≤%|¬1 through |¬u|≤%|¬m|≤%|¬n)|'
6861 >|>!!|2|*/|↔O|↔c|↔L|\|'|;|¬j|¬a|¬z|'|¬d|¬o|¬n|¬e|'
6867 1!|;!Terminate if |εd|4α=↓|41.|'>|>!!|2|*/|↔O|↔c|↔L|\|'
6874 |;|¬e|¬n|¬n|¬i|'|¬n|'A!|;!|πrI1|4|"o|4|εj|4α_↓|4n|4α_↓|41;
6879 j|4|¬L|41.|'>|π|>!!|2|*/|↔O|↔c|↔C|\|'|;|¬e|¬n|¬t|¬a|'
6885 |¬o|'|εA!|;!r|4|¬L|40.|'>|>!!|2|π|*/|↔O|↔c|↔o|\|'
6891 |¬1|¬h|'|¬l|¬d|¬x|'|¬u|≤%|¬m|≤%|¬n|≤%|¬1|¬,|¬1|'
6894 |εAN!|;!|πrAX|4|¬L|4|εrb|4α↓|4u|βm|βα+↓|βj.|'
6896 >|π|>!!|2|*/|↔O|↔c|↔p|\|'|;|¬d|¬i|¬v|'|¬d|'|εAN!|;
6903 >|>|π!!|2|*/|↔O|↔c|↔l|\|'|;|¬s|¬t|¬a|'|¬u|≤%|¬m|≤%|¬n|≤%|¬1|¬
6908 ,|¬1|'|εAN!|;>|π|>!!|2|*/|↔O|↔c|↔m|\|'|;|¬s|¬l|¬a|¬x|'
6915 |¬5|'|εAN!|;!r|4|¬L|4(rb|4α↓|4u|βm|βα↓|βj)|πmod|4|εd.|π|'
6918 >|>!!|2|*/|↔O|↔O|↔c|\|'|;|¬i|¬n|¬c|¬2|'|¬1|'|εAN!|;
6925 !j|4|¬L|4j|4α↓|41.|'>|>|π!!|2|*/|↔O|↔O|↔O|'|\|;
6930 |¬j|¬2|¬n|'|¬1|¬B|'|εAN!|;!|πRepeat for 1|4|¬E|4|εj|4|¬E|4n.
6935 |'>{A9}|πAt this point, the division routine
6943 is complete; and by the next exercise, register
6951 AX is zero.|'{A3}|≡2|≡7|≡.|9|4It is |εde|4|πmod|4|εdv|4α=↓|4
6956 d(u|4|πmod|4|εv).|'{A3}|π|≡2|≡8|≡.|9|4For convenience,
6959 let us assume |εv |πhas a decimal point at the
6969 left, that is, |εvN46α=*?*?*?*?{A3}|≡2|≡7|≡.|9|4It
6973 is |εde|4|πmod|4|εdv|4α=↓|4d(u|4|πmod|4|εv).|'
6975 {A3}|π|≡2|≡8|≡.|9|4For convenience, let us assume
6980 |εv |πhas a decimal point at the left, that is,
6990 |εv|4α=↓|4(v|β0|β.v|β1|β2|4.|4.|4.). |πAfter
6992 step N1 we have |f1|d32|)|4|¬E|4|εv|4|¬W|41|4α↓|41/b:
6997 |πfor|'{A9}|εv|↔d|(b|4α+↓|41|d2v|β1|4αt↓|41|)|↔f|4|∂|¬E|4|(v
6998 (b|4α+↓|41)|d2v|β1|4α+↓|41|)|4α=↓|4|(v(1|4α+↓|41/b)|d2(1/b)(
6998 v|β1|4α↓|41)|)|4|¬W|41|4α+↓|4|(1|d2b|)|1|1,|;
6999 |πand|'|ε| v|↔d|(b|4α+↓|41|d2v|β1|4α+↓|41|)|↔f|4|L|¬R|4|(v(b
7000 |4αt↓|41|4α_↓|4v|β1)|d2v|β1|4α+↓|41|)|4|¬R|4|(1|d2b|)|4|(v|β
7000 1(b|4α+↓|41|4α_↓|4v|β1)|d2v|β1|4α+↓|41|)|1|1.>
7001 {A9}|πThe latter quantity takes its smallest
7007 value when |εv|β1|4α=↓|41, |πsince it is a convex
7015 function and the other extreme value is greater.|'
7023 !!|2The formula in step N2 may be written|'{A9}|εv|4|¬L|4|↔d
7031 |(b(b|4α+↓|41)|d2v|β1|4α+↓|41|)|↔f|1|1|(v|d2b|)|1|1,|;
7032 {A9}|πso we see as above that |εv |πwill never
7041 become |→|¬R1|4α+↓|41/|εb.|π|'!!|2The minimum
7045 value of |εv |πafter one iteration of step N2
7054 is |→|¬R|'{A9}|9|4|↔a|(|εb(b|4α+↓|41)|4α_↓|4v|β1|d2v|β1|4α+↓
7056 |41|)|↔s|1|1|(v|d2b|)|4|¬R|4|↔a|(b(b|4α+↓|41)|4α_↓|4v|β1|d2v
7056 |β1|4α↓|41|)|↔s|1|1|(v|β1|d2b|β2|)|4|∂α=↓|4|↔a|(b(b|4α+↓|41)
7056 |4α+↓|41|4α_↓|4t|d2t|)|↔s|↔a|(t|4α_↓|41|d2b|g2|)|↔s|'
7057 {A4}|Lα=↓|41|4α+↓|4|(1|d2b|)|4α↓|4|(2|d2b|g2|)|4α_↓|4|(1|d2b
7057 |g2|)|1|1|↔at|4α+↓|4|(b(b|4α+↓|41)|4α+↓|41|d2t|)|↔s,>
7058 {A9}|πif |εt|4α=↓|4v|β1|4α+↓|41. |πThe minimum
7062 of this quantity occurs for |εt|4α=↓|4b/2|4α+↓|41;
7068 |πa lower bound is |ε1|4α_↓|43/2b. |πHence |εv|β1|4|¬R|4b|4α
7074 _↓|42, |πafter one iteration of step N2. Finally,
7082 we have |ε(1|4α_↓|43/2b)(1|4αt↓|41/b)|g2|4|¬Q|41,
7085 |πwhen |εb|4|¬R|45, |πso at most two more iterations
7093 are needed. The assertion is easily veri_ed when
7101 |εb|4|¬W|45.|'{A3}|π|≡2|≡9|≡.|9|4True, since
7104 |ε(u|βj|4.|4.|4.|4u|βj|βα+↓|βn)|βb|4|¬W|4v. |π(But
7106 in Program D, |εu|βj |πis left as |εb|4α_↓|41
7114 |πif step D6 is necessary, since there was no
7123 need to reset |εu|βj |πwhen it was never being
7132 used in the subject calculation.)|'{A3}|≡3|≡0|≡.|9|4In
7138 Algorithms A and S, such overlap is possible
7146 if the algorithms are rewritten slightly; e.g.,
7153 in Algorithm A, we could rewrite step A2 thus:
7162 ``Set |εt|4|¬L|4u|βj|4α+↓|4v|βj|4α+↓|4k, w|βj|4|¬L|4t|4|πmod
7164 |4|εb, k|4|¬L|4|"lt/b|"L.''|'|π!!|2In Algorithm
7168 M, |εv|βj |πmay be in the same location as |εw|βj.
7178 |πIn Algorithm D, it is most convenient (as in
7187 Program D, exercise 26) to let |εr|β1|4.|4.|4.|4r|βn
7194 |πbe the same as |εu|βm|βα+↓|β1|4.|4.|4.|4u|βm|βα+↓|βn;
7199 |πand we can also have |εq|β0|4.|4.|4.|4q|βm
7205 |πthe same as |εu|β0|4.|4.|4.|4u|βm, |πprovided
7210 that no alteration of |εu|βj |πis made in step
7219 D6. (Such an alteration is unnecessary, as mentioned
7227 in exercise 29.)|'{A3}|≡3|≡1|≡.|9|4One possibility
7232 is this, if we consider the situation of Fig.
7241 6 with |εu|4α=↓|4u|βju|βj|βα+↓|β1|4.|4.|4.|4u|βj|βα+↓|βn
7244 |πas in Algorithm D: If the leading nonzero digits
7253 of |εu |πand |εv |πhave the same sign, set |εr|4|¬L|4u|4α_↓|
7262 4v, q|4|¬L|41; |πotherwise set |εr|4|¬L|4u|4α+↓|4v,
7267 q|4|¬L|4|→α_↓1. |πNow if |ε|¬Gr|¬G|4|¬Q|4|¬Gu|¬G,
7271 |πor if |ε|¬Gr|¬G|4α=↓|4|¬Gu|¬G |πand the _rst
7277 nonzero digit of |εu|βj|βα+↓|βn|βα+↓|β1|4.|4.|4.|4u|βm|βα+↓|
7280 βn |πhas the same sign as the _rst nonzero digit
7290 of |εr, |πset |εq|4|¬L|40; |πotherwise set |εu|βj|4.|4.|4.|4
7296 u|βj|βα+↓|βn|4|¬L|4r.|'{A3}|π|≡3|≡6|≡.|9|4Values
7298 to 1000 decimal and 1100 octal places have been
7307 computed by R. P. Brent, Tech. Rep. 47, Comp.
7316 Centre, Australian Nat. Univ., Canberra, 1975.|'
7322 {A25}{H10L12}|*/|\|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨3|∨.|∨2|'
7323 {A11}{H9L11}|9|1|≡1|≡.|9|4The solution is unique
7327 since 7|4|¬O|411|4|¬O|413|4α=↓|41001. The ``constructiave''
7331 proof of Theorem C tells us that the answer is
7341 {H11}({H9}(11|4|¬O|413)|g6|4α+↓|4(7|4|¬O|413)|g1|g0|4α+↓|45|
7341 4|¬O|4(7|4|¬O|411)|g1|g2{H11}){H9}mod|41001.
7342 This answer is perhaps not explicit enough*3 By
7350 (23) we have |εv|β1|4α=↓|41, v|β2|4α=↓|4(6|4α_↓|41)|4|¬O|48|
7354 4|πmod|411|4α=↓|47, v|β3|4α=↓|4{H11}({H9}(5|4α_↓|41)|4|¬O|42
7355 |4α_↓|47{H11}){H9}|4|¬O|46|4mod|413|4α=↓|46,
7356 so |εu|4α=↓|46|4|¬O|47|4|¬O|411|4α+↓|47|4|¬O|47|4α+↓|41|4α=↓
7357 |4512.|'{A3}|π|9|1|≡2|≡.|9|4Yes (by the ``constructive''
7362 proof given, but not by the ``nonconstructive''
7369 proof).|'{A3}|9|1|≡3|≡.|9|4|εu|4|"o|4u|βi (|πmodulo
7372 |εm|βi) |πimplies that |εu|4|"o|4u|βi |π{H11}({H9}modulo|4gc
7376 d(|εm|βi,|4m|βj){H11}){H9}, |πso the condition
7380 |εu|βi|4|"o|4u|βj {H11}({H9}|πmodulo gcd(|εm|βi,|4m|βj){H11}
7382 ){H9} |πmust surely hold if there is a solution.
7391 Furthermore if |εu|4|"o|4v |π(modulo |εm|βj)
7396 |πfor all |εj, |πthen |εu|4α_↓|4v |πis a multiple
7404 of lcm(|εm|β1,|4.|4.|4.|4,|4m|βr)|4α=↓|4m; |πhence
7407 there is at most one solution.|'!!|2The proof
7415 can now be completed in a nonconstructive manner
7423 by counting the number of di=erent sets |ε(u|β1,|4.|4.|4.|4,
7430 |4u|βr) |πsatisfying the conditions 0|4|¬E|4u|βj|4|¬W|4m|βj
7435 |πand |εu|βi|4|"o|4u|βj {H11}({H9}|πmodulo gcd|ε(m|βi,|4m|βj
7438 ){H11}){H9}. If this number is |εm, |πthere must
7446 be a solution since |ε(u|4|πmod.|εm|β1,|4.|4.|4.|4,|4u|4|πmo
7450 d|4|εm|βr) |πtakes on |εm |πdistinct values as
7457 |εu |πgoes from |εa |πto |εa|4α+↓|4m. |πAssume
7464 that |εu|β1,|4.|4.|4.|4,|4u|βr|βα_↓|β1 |πhave
7467 been chosen satisfying the given conditions;
7473 we must now pick |εu|βr|4|"o|4u|βj |π{H11}({H9}modulo
7479 gcd|ε(m|βj,|4m|βr){H11}){H9} for 1|4|¬E|4j|4|¬W|4r,
7482 |πand by the generalized Chinese Remainder Theorem
7489 for |εr|4α_↓|41 |πelements there are|'{A9}|εm|βr/|πlcm{H11}(
7494 {H9}gcd|ε(m|β1,|4m|βr),|4.|4.|4.|4,|4|πgcd|ε(m|βr|βα_↓|β1,|4
7494 m|βr){H11}){H9}|4|∂α=↓|4m|βr/|πgcd{H11}({H9}lcm|ε(m|β1,|4.|4
7494 .|4.|4,|4m|βr|βα_↓|β1),|4m|βr{H11}){H9}|'{A4}|Lα=↓|4|πlcm(|ε
7495 m|β1,|4.|4.|4.|4,|4m|βr)/|πlcm(|εm|β1,|4.|4.|4.|4,|4m|βr|βα_
7495 ↓|β1)>{A9}|πways to do this. [This proof is based
7504 on identities (10), (11), (12), and (14) of Section
7513 4.5.2.]|'!!|2A constructive proof [A. S. Fraenkel,
7520 |εProc. AMS |≡1|≡5 (1963), 790<791] |πgeneralizing
7526 (24) can be given as follows. Let |εM|βj|4α=↓|4|πlcm|ε(m|β1,
7533 |4.|4.|4.|4,|4m|βj); |πwe wish to _nd |εu|4α=↓|4v|βrM|βr|βα_
7538 ↓|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4v|β2M|β1|4α+↓|4v|β1,
7539 |πwhere 0|4|¬E|4|εv|βj|4|¬W|4M|βj/M|βj|βα_↓|β1.
7541 |πAssume that |εv|β1,|4.|4.|4.|4,|4v|βj|βα_↓|β1
7544 |πhave already been determined; then we must
7551 solve the congruence|'{A9}|εv|βjM|βj|βα_↓|β1|4α+↓|4v|βj|βα_↓
7554 |β1M|βj|βα_↓|β2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4v|β1|4|"o|4u|βj!|π
7554 (modulo|4|εm).|;{A9}|πGere |εv|βj|βα_↓|β1M|βj|βα_↓|β2|4α+↓|4
7556 |¬O|4|¬O|4|¬O|4α+↓|4v|β1|4|"o|4u|βi|4|"o|4u|βj
7557 |π{H11}({H9}modulo gcd|ε(m|βi,|4m|βj){H11}){H9}
7559 |πfor |εi|4|¬W|4j |πby hypothesis, so |εc|4α=↓|4u|βj|4α_↓|4(
7564 v|βj|βα_↓|β1M|βj|βα_↓|β2|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4v|β1)
7565 |πis a multiple of|'|Hβ*?*?*?{U0}{H9L11M29}|π58320#Computer
folio 761 galley 8
7570 Programming!(Knuth/Addison-Wesley)!f. 761!Ans!g.
7572 8|'{A9}lcm{H11}({H9}gcd(|εm|β1,|4m|βj),|4.|4.|4.|4,|4|πgcd|ε
7573 (m|βj|βα_↓|β1,|4m|βj){H11}){H9}|4α=↓|4|πgcd(|εM|βj|βα_↓|β1,|
7573 4m|βj)|4α=↓|4d|βj.|;{A9}|πWe therefore must solve
7578 |εv|βjM|βj|βα_↓|β1|4|"o|4c |π(modulo |εm|βj).
7581 |πBy Euclid's algorithm there is a number |εc|βj
7589 |πsuch that |εc|βjM|βj|βα_↓|β1|4|"o|4f|βj(|πmodulo
7592 |εm|βj); |πhence we may take|'{A9}|εv|βj|4α=↓|4(c|βjc)/d|βj|
7597 4|πmod|ε(m|βj/d|βj).|;{A9}|πNote that, as in
7602 the nonconstructive proof, we have |εm|βj/d|βj|4α=↓|4M|βj/M|
7607 βj|βα_↓|β1.|'{A3}|π|9|1|≡4|≡.|9|4(After |εm|β4|4α=↓|491|4α=↓
7609 |47|4|¬O|413, |πwe have used up all products
7616 of two or more odd primes that can be less than
7627 100, so |εm|β5,|4.|4.|4. |πmust all be prime.)|'
7634 {A9}|εm|β7|h|β7|n|4|∂α=↓|479,!m|β8|h|β8|n|4|∂α=↓|473,!m|β9|h
7634 |β9|n|4|∂α=↓|471,!m|β1|β0|4|∂α=↓|467,!m|β1|β1|4|∂α=↓|461,|;
7635 {A4}| m|β1|β2|4|Lα=↓|459,| m|β1|β3|4|Lα=↓|453,| m|β1|β4|4|Lα
7635 =↓|447,| m|β1|β5|4|Lα=↓|443,| m|β1|β6|4|Lα=↓|441,>
7636 {A4}| m|β1|β7|4|Lα=↓|437,| m|β1|β8|4|Lα=↓|431,| m|β1|β9|4|Lα
7636 =↓|429,| m|β2|β0|4|Lα=↓|423,| m|β2|β1|4|Lα=↓|417,>
7637 {A9}|πand then we are stuck |ε(m|β2|β2|4α=↓|41
7643 |πdoes no good).|'{A3}|9|1|≡5|≡.|9|4No; an obvious
7649 upper bound is|'{A3}3|g45|g27|g211|g1|4|¬O|4|¬O|4|¬O|4α=↓|4|
7652 ≥u|uc|)|εp|1|1|πodd|d|εp|1|1|πprime|)|4|εp|g|"l|π|gl|go|gg|ε
7652 |rp|1|1|g1|g0|g0|g|"L.|;{A9}|πThis upper bound
7656 is attained if we choose |εm|β1|4α=↓|43|g4, m|β2|4α=↓|45|g2,
7662 |πetc. (It is more di∃cult, however, to maximize
7672 |εm|β1|4.|4.|4.|4m|βr |πwhen |εr |πis _xed, or
7678 to maximize |εm|β1|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4m|βr
7681 |πas we would attempt to do using moduli |ε2|gm|rj|4α_↓|41.)
7689 |'{A3}|π|9|1|≡6|≡.|9|4a) If |εe|4α=↓|4f|4α+↓|4kg,
7693 |πthen |ε2|ge|4α=↓|42|gf(2|gg)|gk|4|"o|42|gf|4|¬O|41|gk
7695 |π(modulo 2|ε|gg|4α_↓|41). |πSo if |ε2|ge|4|"o|42|gf
7700 |π(modulo 2|ε|gg|4α_↓|41), |πthen 2|ε|ge|1|1|π|gm|go|gd|1|1|
7703 ε|gg|4|"o|42|gf|1|1|π|gm|go|gd|1|1|ε|gg |π(modulo
7705 2|ε|gg|4α_↓|41), |πand since the latter quantities
7711 lie between zero and |ε2|gg|4α_↓|41 |πwe must
7718 have |εe |πmod|4|εg|4α_↓|4f |πmod|4|εg.|'!!|2|πb)|9By
7723 part (a),|'{A9}(1|4α+↓|42|ε|gd|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|g
7725 (|gc|gα_↓|g1|g)|gd)|4|¬O|4(2|ge|4α_↓|41)|4|"o|4(1|4α+↓|42|gd
7725 |4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|42|g(|gc|gα_↓|g1|g)|gd)|4|¬O|4(2|g
7725 d|4α_↓|41)|'{A3}α=↓|42|gc|gd|4α_↓|41|4|"o|42|gc|gc|4α_↓|41|4
7726 |¬o|42|g1|4α_↓|41|4α=↓|41!|π(modulo 2|ε|gf|4α_↓|41).|?
7728 {A3}|π|9|1|≡7|≡.|9|4{H11}({H9}|εu|βj|4α_↓|4(v|β1|4α+↓|4m|β1(
7728 v|β2|4α+↓|4m|β2(v|β3|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4m|βj|βα_↓|β2v
7728 |βj|βα_↓|β1)|4|¬O|4|¬O|4|¬O)){H11}){H9}c|β1|βj|4.|4.|4.|4c|β
7728 (|βj|βα_↓|β1|β)|βj|'!!!!|∂α=↓|4(u|βj|4α_↓|4v|β1)c|β1|βj|4.|4
7729 .|4.|4c|β(|βj|βα_↓|β1|β)|βj|4α_↓|4m|β1v|β2c|β1|4.|4.|4.|4c|β
7729 (|βj|βα_↓|β1|β)|βj|4α_↓|4|¬O|4|¬O|4|¬O|4|'{A3}α_↓|4m|β1|4.|4
7730 .|4.|4m|βj|βα_↓|β2v|βj|βα_↓|β1c|β1|βj|4.|4.|4.|4c|β(|βj|βα_↓
7730 |β1|β)|βj|?{A3}|L|"o|4(u|βj|4α_↓|4v|β1)c|β1|βj|4.|4.|4.|4c|β
7731 (|βj|βα_↓|β1|β)|βj|4α_↓|4v|β2c|β2|βj|4.|4.|4.|4c|β(|βj|βα_↓|
7731 β1|β)|βj|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα_↓|β1c|β(|βj|βα_↓|
7731 β1|β)|βj>{A3}|Lα=↓|4{H11}({H9}|¬O|4|¬O|4|¬O|4((u|βj|4α_↓|4v|
7732 β1)c|β1|βj|4α_↓|4v|β2)c|β2|βj|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj
7732 |βα_↓|β1{H11}){H9}c|β(|βj|βα_↓|β1|β)|βj!|π(modulo
7733 |εm|βj).>{A9}|π!!|2This method of rewriting the
7739 formulas uses the same number of arithmetic operations
7747 and fewer constants; but the number of constants
7755 is fewer only if we order the moduli so that
7765 |εm|β1|4|¬W|4m|β2|4|¬W|4|¬O|4|¬O|4|¬O|4|¬W|4m|βr,
7766 |πotherwise we would need a table of |εm|βi |πmod
7775 |εm|βj. |πThis ordering of the moduli might seem
7783 to require more computation than if we made |εm|β1
7792 |πthe largest, |εm|β2 |πthe next largest, etc.,
7799 since there are many more operations to be done
7808 modulo |εm|βr |πthan modulo |εm|β1; |πbut sine
7815 |εv|βj |πcan be as large as |εm|βj|4α_↓|41, |πwe
7823 are better o= with |εm|β1|4|¬W|4m|β2|4|¬W|4|¬O|4|¬O|4|¬O|4|¬
7827 W|4m|βr |πin (23) also. So this idea appears
7835 to be preferable to the formulas in the text,
7844 although the formulas in the text are advantageous
7852 when the moduli have the form (14), as shown
7861 in Section 4.3.3.|'{A3}|9|1|≡8|≡.|9|4|εm|βj|βα_↓|β1|4.|4.|4.
7864 |4m|β1v|βj|4|"o|4m|βj|βα_↓|β1|4.|4.|4.|4m|β1{H11}({H9}|¬O|4|
7864 ¬O|4|¬O|4((u|βj|4α_↓|4v|β1)c|β1|βj|4α_↓|4v|β2)c|β2|βj|4α_↓|4
7864 |¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα_↓|β1{H11}){H9}c|β(|βj|βα_↓|β1|β)
7864 |βj|4|"o|4m|βj|βα_↓|β2|4.|4.|4.|4m|β1{H11}({H9}|¬O|4|¬O|4|¬O
7864 |4(u|βj|4α_↓|4v|β1)c|β1|βj|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα
7864 _↓|β2{H11}){H9}c|β(|βj|βα_↓|β2|β)|βj|4α_↓|4v|βj|βα_↓|β1m|βj|
7864 βα_↓|β2|4.|4.|4.|4m|β1|4|"o|4|¬O|4|¬O|4|¬O|4|"o|4u|βj|4α_↓|4
7864 v|β1|4α_↓|4v|β2m|β1|4α_↓|4|¬O|4|¬O|4|¬O|4α_↓|4v|βj|βα_↓|β1m|
7864 βj|βα_↓|β2|4.|4.|4.|4m|β1!(|πmodulo |εm|βj).|'
7866 {A3}|9|1|≡9|≡.|9|4u|βr|4|¬L|4{H11}({H9}(.|4.|4.|4(v|βrm|βr|β
7866 α_↓|β1|4α+↓|4v|βr|βα_↓|β1)m|βr|βα_↓|β2|4α+↓|4|¬O|4|¬O|4|¬O)m
7866 |β1|4α+↓|4v|β1{H11}){H9}|4|πmod|4|εm|βr,|4.|4.|4.|4,|'
7867 u|β2|4|¬L|4(v|β2m|β1|4α+↓|4v|β1|πmod|4|εm|β2,|4u|β1|4|¬L|4v|
7867 β1|4|πmod|4|εm|β1.|?{A9}|π(The computation should
7871 be done in this order, if we want to let |εu|βj
7882 |πand |εv|βj |πshare the same memory locations
7889 as is possible in (23).{H11}){H9}|'{A3}|≡1|≡0|≡.|9|4If
7895 we rede_ne the ``mod'' operator so that it produces
7904 residues in the symmetrical range, the basic
7911 formulas (2), (3), (4) for arithmetic and (23),
7919 (24) for conversiond remain the same, and the
7927 number |εu |πin (24) lies in the desired range
7936 (10). {H11}({H9}Here (24) is a |εbalanced mixed
7943 radix |πnotation, generalizing ``balanced-ternary''
7947 notation.{H11}){H9} The comparison of two numbers
7953 may still be done from left to right, in the
7963 simple manner described in the text. Furthermore,
7970 it is possible to retain the value |εu|βj |πin
7979 a single computer word, if we have signed magnitude
7988 representation within the computer, even if |εm|βj
7995 |πis almost twice the word size. But the arithmetic
8004 operations analogous to (11) and (12) are more
8012 di∃cult, so it appears that on most computers
8020 this idea would result in slightly slower operation.|'
8028 {A3}|≡1|≡1|≡.|9|4Multiply by|'|ε|(m|4α+↓|41|d22|)|4α=↓|4|↔a|
8030 (m|β1|4α+↓|41|d22|)|1|1,|4.|4.|4.|4,|4|(m|βr|4α+↓|41|d22|)|↔
8030 s.|;|πNote that|'|ε2t|4|¬O|4|(m|4α+↓|41|d22|)|4|"o|4t!|π(mod
8033 ulo|4|εm).|;{A9}|πIn general if |εv |πis relatively
8040 prime to |εm, |πthen we can _nd (by Euclid's
8049 algorithm) a number |εv|¬S|4α=↓|4(v|ur|↔0|)1|),|4.|4.|4.|4,|
8052 4v|ur|↔0|)r|)) |πsuch that |εvv|¬S|4|"o|41 |π(modulo|4|εm);
8057 |πand then if |εu |πis known to be a multiple
8067 of |εv |πwe have |εu/v|4α=↓|4uv|¬S, |πwhere the
8074 latter is computed with modular multiplication.
8080 When |εv |πis not relatively prime to |εm, |πdivision
8089 is much more di∃cult.|'{A3}|π|≡1|≡2|≡.|9|4Obvious
8094 from (11), if we replace |εm|βj |πby |εm.|'{A3}|π|≡1|≡3|≡.|9
8102 |4(a) |εx|g2|4α_↓|4x|4α=↓|4(x|4α_↓|41)x|4|"o|40
8104 |π(modulo 10|ε|gn) |πis equivalent to |ε(x|4α_↓|41)x|4|"o|40
8109 |π(modulo |εp|gn) |πfor |εp|4α=↓|42 |πand 5.
8116 Either |εx |πor |εx|4α_↓|41 |πmust be a multiple
8124 of |εp, |πand then the other is relatively prime
8133 to |εp|gn; |πso either |εx |πor |εx|4α_↓|41 |πmust
8141 be a multiple of |εp|gn. |πIf |εx|4|πmod|4|ε2|gn|4α=↓|4x|4|π
8147 mod|4|ε5|gn|4α=↓|40 |πor 1, we must have |εx|4α=↓|40
8154 |πor 1; hence |εx|4|πmod|4|ε2|gn|4|=|↔6α=↓|4x
8158 |πmod|4|ε5|gn. |π(b) If |εx|4α=↓|4qp|gn|4α+↓|4r,
8162 |πwhere |εr|4α=↓|40 |πor 1, then |εr|4|"o|4r|g2|4|"o|4r|g3,
8168 |πso |ε3x|g2|4α_↓|42x|g3|4|"o|4(6qp|gnr|4α+↓|43r)|4α_↓|4(6qp
8169 |gnr|4α+↓|42r)|4|"o|4r|π(modulo|4|εp|gn). |π(c)
8171 Let |εc|¬S|4α=↓|4{H11}({H9}3(cx)|g2|4α_↓|42(cx)|g3{H11}){H9}
8172 /x|g2|4α=↓|43c|g2|4α_↓|42c|g3x.|'!!|2|π|εNote|*/:|\
8174 |πSince the last |εk |πdigits of an |εn-|πdigit
8182 automorph form a |εk-|πdigit automorph, it makes
8189 sense to speak of the two |¬X-digit automorphs,
8197 |εx |πand 1|4α_↓|4|εx, |πwhich are 10-adic numbers
8204 (cf. exercise 4.1<31). Th*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
8207